https://www.acmicpc.net/problem/3114

 

(1, 1)에서 출발하여 (N, M)에 도착했을 때 사과 + 바나나의 최대를 구하는 문제입니다.

이동은 아래, 오른쪽, 오른쪽 + 아래 만 가능합니다.

 

(x, y) 기준 사과 + 바나나의 합은

1. (x, y) ~ (x - 1, y) 까지는 바나나

2. (x + 1, y) ~ (N, y) 까지는 사과

두개를 더하여 계산합니다.

그렇다면 사과와 바나나의 누적합은 각각 구할 수 있고, 세로별로 누적합을 구하도록 합니다.

 

세팅이 완료되었다면 점화식을 구해봅니다.

이동 가능한 방향이 어떻게 되는지를 이용하면 (x, y) 기준 3개 중 하나를 답으로 가져갈 수 있습니다.

(x - 1, y - 1), (x, y - 1)에서 왔을 경우 y 좌표가 바꼈으므로 이전에 구했던 누적합을 더하면 됩니다.

(x - 1, y)에서 왔을 경우 y좌표가 바뀌지 않았으므로 누적합 범위를 조정해야 합니다.

 

dp 값을 채워나가는 도중에 dp[N][M]보다 커지는 경우가 있을 수 있으니 dp[N][M]를 명시하여 출력해주시면 되겠습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <algorithm>
#define MAX 1501
using namespace std;
 
int sumA[MAX][MAX], sumB[MAX][MAX], dp[MAX][MAX];
int N, M;
 
void func() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (j == 1) {
                dp[i][j] = sumA[N][j] - sumA[i][j];
                continue;
            }
 
            int tmp = sumA[N][j] - sumA[i][j] + sumB[i - 1][j];
            dp[i][j] = max(max(dp[i - 1][j - 1], dp[i][j - 1]) + tmp, dp[i - 1][j] - sumA[i][j] + sumA[i - 1][j]);
        }
    }
 
    cout << dp[N][M] << '\n';
}
 
void input() {
    char ch;
    int x;
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> ch >> x;
            if (ch == 'A') {
                sumA[i][j] = x;
            }
            else {
                sumB[i][j] = x;
            }
            sumA[i][j] += sumA[i - 1][j];
            sumB[i][j] += sumB[i - 1][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 2216 문자열과 점수  (0) 2024.06.28
boj 1354 무한 수열 2  (0) 2024.06.27
boj 11560 다항식 게임  (0) 2024.06.13
boj 28018 시간이 겹칠까?  (0) 2023.08.08
boj 12841 정보대 등산  (0) 2023.07.31

https://www.acmicpc.net/problem/11560

 

약 1년만에 dp 문제입니다. 그동안 게을러 빠졌었네요 ^^..

 

이 문제는 N, M의 범위가 작으므로 미리 모든 값을 구할 수 있습니다.

그 다음 입력받는대로 출력만 하면 되는 방식입니다.

 

우선 점화식은 N을 직접 늘려가면서 다항식을 구해보시면 충분히 나올 수 있습니다.

 

여기서 알 수 있는 점화식은

i번째 다항식의 j번 계수는 [i - 1번째 다항식]의 [j - i번째 계수] ~ [j번째 계수]까지의 합으로 구할 수 있습니다.

그렇다면 점화식은

dp[i][j] = dp[i - 1][j - i] + dp[i - 1][j - i + 1] + ... + dp[i - 1][j]

이렇게 될 것이고, 코드로 그대로 옮겨주시면 되겠습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <algorithm>
#define MAX_N 21
#define MAX_M 211
using namespace std;
typedef long long ll;
 
ll dp[MAX_N][MAX_M];
int N, M;
 
void init() {
    dp[1][0] = 1LL;
    dp[1][1] = 1LL;
    for (int i = 2; i < MAX_N; i++) {
        for (int j = 0; j <= (i * (i + 1)) >> 1; j++) {
            for (int k = max(0, j - i); k <= j; k++) {
                dp[i][j] += dp[i - 1][k];
            }
        }
    }
}
 
void func() {
    cout << dp[N][M] << '\n';
}
 
void input() {
    cin >> N >> M;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    init();
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
    }
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 1354 무한 수열 2  (0) 2024.06.27
boj 3114 사과와 바나나  (0) 2024.06.13
boj 28018 시간이 겹칠까?  (0) 2023.08.08
boj 12841 정보대 등산  (0) 2023.07.31
boj 25427 DKSH를 찾아라  (0) 2023.05.21

https://www.acmicpc.net/problem/3758

 

구현문제는 문제만 잘 읽고 이해한다면 어렵지 않게 해결할 수 있습니다.

물론 저는 읽고 이해하는게 어렵습니다 ^^

 

팀 순위를 정하는 방식은

각 문제들을 해결하면서 얻은 점수의 합이 되겠고,

최종 점수가 같으면 풀이를 제출한 횟수가 적은 팀이 우선
제출 횟수도 같으면 마지막 제출 시간이 더 빠른 팀이 우선순위를 높게 가져갑니다.

 

그렇다면 입력단계에서 구해야할건

먼저 점수의 합은 입력으로 들어온 각 팀마다 문제별 최고점수를 저장하면 구할 수 있고,

제출한 횟수는 팀이 입력되는 횟수를 카운팅하여 구할 수 있고,

마지막 제출 시간은 입력들의 인덱스를 갱신하기만 하면 구할 수 있습니다.

 

이제 위에서 구한 정보들로 순위를 정할 수 있습니다.

문제에서는 본인의 순위만 출력하면 되기 때문에 본인보다 순위가 높은 팀을 카운팅하면 구할 수 있습니다.

 

위에서 언급한 팀 순위를 정하는 방식을 이용하여 특정 팀이 본인보다 높은지 확인해주시면 되겠습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 101
using namespace std;
 
int scores[MAX][MAX];
int tries[MAX];
int cnts[MAX];
int N, K, T, M;
 
int getScore(int team) {
    int ret = 0;
    for (auto score : scores[team]) {
        ret += score;
    }
    return ret;
}
 
bool isBetter(int team) {
    int x = getScore(T);
    int y = getScore(team);
    if (x == y) {
        if (cnts[T] == cnts[team]) return tries[T] > tries[team];
        return cnts[T] > cnts[team];
    }
    return x < y;
}
 
void func() {
    int ret = 0;
    for (int i = 1; i <= N; i++) {
        if (i == T) continue;
        ret += isBetter(i);
    }
    cout << ret + 1 << '\n';
}
 
void input() {
    int id, no, s;
    cin >> N >> K >> T >> M;
    for (int i = 1; i <= M; i++) {
        cin >> id >> no >> s;
        scores[id][no] = max(scores[id][no], s);
        cnts[id]++;
        tries[id] = i;
    }
}
 
void init() {
    for (int i = 1; i <= N; i++) {
        memset(scores[i], 0, sizeof(scores[i]));
    }
    memset(cnts, 0, sizeof(cnts));
    memset(tries, 0, sizeof(tries));
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
        init();
    }
 
    return 0;
}
 cs

'algorithm > Implementation' 카테고리의 다른 글

boj 1756 피자 굽기  (0) 2024.08.08
boj 17143 낚시왕  (0) 2021.04.23
boj 20207 달력  (0) 2021.04.22
boj 17144 미세먼지 안녕!  (0) 2021.04.14
boj 2564 경비원  (0) 2021.04.13

 

https://www.acmicpc.net/problem/1377

 

정렬 문제처럼 보이지만 아이디어를 요구하는 애드혹 문제입니다.

이 문제는 버블 소트의 특징을 이해하고 있어야 풀 수 있습니다.

이해하고 있어도 문제를 해결하는데 필요한 아이디어를 얻기까지 꽤 오랜 시간이 걸렸습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool changed = false;
for (int i=1; i<=N+1; i++) {
    changed = false;
    for (int j=1; j<=N-i; j++) {
        if (A[j] > A[j+1]) {
            changed = true;
            swap(A[j], A[j+1]);
        }
    }
    if (changed == false) {
        cout << i << '\n';
        break;
    }
}
 cs

우선 문제에 작성되어있는 코드로 i가 어떻게 출력되는지 찾아야 합니다.

우선 위 코드는 앞에 위치한 수가 자신보다 크다면 두 수의 위치를 변경하는 방식으로 구현된 정렬입니다.

이 로직에 의하면 범위 내 상대적으로 큰 수는 뒤쪽으로 이동하고, 상대적으로 작은 수는 앞쪽으로 이동하게 됩니다.

 

여기서 잡을 수 있는건 뒤쪽으로는 무한정 이동이 가능하지만 앞쪽으로는 한 칸만 이동이 가능하다는 것입니다.

즉 i가 한 번 돌아갈 때마다 상대적으로 작은 수는 앞쪽으로 한 칸 이동한다는 말이 되고, 앞쪽으로 가장 많이 움직인 횟수를 구하면 답을 얻을 수 있습니다.

 

여기까지 오셨다면 코드를 작성할 수 있습니다.

앞쪽으로 얼마나 이동했는지에 대해,

최초 위치한 인덱스를 저장할 필요가 있을 것이고,

정렬 후에 위치한 인덱스만 있다면 답을 구할 수 있습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <algorithm>
#define MAX 500001
using namespace std;
typedef pair<int, int> pii;
 
pii list[MAX];
int N;
 
void func() {
    sort(list, list + N);
 
    int ret = 0;
    for (int i = 0; i < N; i++) {
        ret = max(ret, list[i].second - i);
    }
 
    cout << ret + 1 << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first;
        list[i].second = i;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > ad-hoc' 카테고리의 다른 글

boj 5527 전구 장식  (0) 2024.07.30
boj 14864 줄서기  (0) 2024.07.26
boj 2381 최대 거리  (0) 2024.07.25
boj 14675 단절점과 단절선  (0) 2024.07.23
boj 27468 2배 또는 0.5배  (0) 2024.07.22

https://www.acmicpc.net/problem/17131

 

17131번: 여우가 정보섬에 올라온 이유

첫 줄에 별의 개수 N이 주어진다. 그 다음 줄부터 N개의 줄에 걸쳐 별의 좌표 x y가 주어진다.

www.acmicpc.net

알고리즘 정말 오랜만이네요.

 

만들어야 하는 별자리는 V 모양이며, V를 회전한 모양은 포함하지 않습니다. (ex. < > ^ ㄱ ㄴ 모양은 X)

여기서 가로를 x, 세로를 y 축이라고 가정했을 때

예시 기준 a, b, c만 별자리로 인정할 수 있습니다.

 

그리고 문제에서도 a.x < b.x < c.x이고 a.y > b.y < c.y 라고 친절히 설명도 해줍니다.

이 조건에서 라인 스위핑 기법을 활용하기 위해 y 값 기준 내림차순 정렬이 필요하다는 것을 알 수 있습니다.

그러면 같은 y값들을 가지고 먼저 놓여진 별들 중 x 값이 작은 별들의 갯수와 x 값이 큰 별들의 갯수를 곱하면 별자리의 갯수를 구할 수 있습니다.

어떤 정해진 범위 내에서 특정 범위의 값을 구한다고 했을때 구간합을 떠올릴 수 있습니다.

구간합을 구하는 알고리즘은 세그먼트 트리가 있습니다.

그러면 이 문제는 세그먼트 트리 + 라인 스위핑을 활용하여 해결할 수 있습니다.

 

로직의 순서는

1. 위에서 설명한것처럼 y 좌표 기준으로 내림차순 정렬합니다.

2. 같은 y값을 가진 별들을 가지고 x 값이 작은/큰 별들의 갯수를 구합니다.

3. 그 다음 같은 y값을 가진 별들을 한꺼번에 트리에 업데이트를 합니다.

 

이게 끝이지만 주의할점은

같은 y값을 가진 모든 별들이 2번 과정이 끝난 후에 3번 과정을 같이 진행해야합니다.

이 풀이의 핵심은 2번 과정에 들어왔을때 트리에 있는 값들은 모두 자신보다 y 값이 큰 별 이라는 것입니다.

그래서 저는 같은 y값을 가진 별들을 벡터에 넣어주고, 3번 과정에서 한꺼번에 업데이트를 했습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 200001
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
ll tree[MAX << 3];
pii list[MAX];
int N;
 
bool cmp(pii a, pii b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second > b.second;
}
 
ll update(int node, int l, int r, int idx) {
    if (idx < l || r < idx) return tree[node];
    if (l == r) {
        return tree[node] = tree[node] + 1;
    }
 
    int m = (l + r) >> 1;
    return tree[node] = update(node << 1, l, m, idx) + update((node << 1) + 1, m + 1, r, idx);
}
 
ll query(int node, int l, int r, int s, int e) {
    if (s <= l && r <= e) return tree[node];
    if (e < l || r < s) return 0LL;
 
    int m = (l + r) >> 1;
    return query(node << 1, l, m, s, e) + query((node << 1) + 1, m + 1, r, s, e);
}
 
void func() {
    sort(list + 1, list + 1 + N, cmp);
 
    ll ret = 0;
    int pre = list[1].second;
    vector<int> v;
    for (int i = 1; i <= N; i++) {
        int m = list[i].first;
        if (pre == list[i].second) {
            v.push_back(m);
        }
        else {
            for (auto x : v) {
                update(1, 0, (MAX - 1) << 1, x);
            }
            v.clear();
            pre = list[i].second;
            v.push_back(m);
        }
        ret = (ret + query(1, 0, (MAX - 1) << 1, 0, m - 1) * query(1, 0, (MAX - 1) << 1, m + 1, (MAX - 1) << 1)) % MOD;
    }
 
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i].first >> list[i].second;
        list[i].first += (MAX - 1);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > SegmentTree' 카테고리의 다른 글

boj 8330 순열  (0) 2024.07.21
boj 1517 버블 소트  (0) 2024.06.16
boj 12895 화려한 마을  (0) 2022.09.07
boj 10167 금광  (0) 2022.09.02
boj 16993 연속합과 쿼리  (0) 2022.08.29

https://www.acmicpc.net/problem/28018

 

28018번: 시간이 겹칠까?

댓글을 달아준 학생 수 $N$이 주어진다. $(1\leq N\leq 100\,000)$ 다음 $N$개 줄에는 각 학생의 좌석 배정 시각 $S$와 종료 시각 $E$가 주어진다. $(1\leq S\leq E\leq 1\,000\,000)$ 다음 줄에는 특정한 시각의 개수

www.acmicpc.net

특정 시간에 학생이 몇명 채워져 있는지 구하는 문제입니다.

이 문제는 학생들이 머무르는 구간 l ~ r이 주어집니다.

l ~ r 구간을 모두 채워주어야 하며, 매 쿼리의 l ~ r 구간의 누적을 구하면 O(N^2)의 시간이 걸려 TLE가 발생합니다.

매 쿼리마다 누적합을 갱신하지 않고, 시작과 끝에만 표시하여 한꺼번에 누적합을 구할 수 있는 imos 기법을 활용합니다.

 

학생은 l 시간에 들어와서 r 시간까지 머무릅니다.

따라서 학생이 존재하기 시작하는 l 시간에 +1, 학생이 없는 시간인 r + 1 시간에 -1을 누적합니다.

마지막에 누적합을 갱신하면 O(N) 시간 만으로도 문제를 해결할 수 있습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#define MAX 1000001
using namespace std;
 
int dp[MAX];
int N, M;
 
void func() {
    for (int i = 1; i < MAX; i++) {
        dp[i] += dp[i - 1];
    }
 
    int x;
    cin >> M;
    while (M--) {
        cin >> x;
        cout << dp[x] << '\n';
    }
}
 
void input() {
    int l, r;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> l >> r;
        dp[l]++;
        dp[r + 1]--;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 3114 사과와 바나나  (0) 2024.06.13
boj 11560 다항식 게임  (0) 2024.06.13
boj 12841 정보대 등산  (0) 2023.07.31
boj 25427 DKSH를 찾아라  (0) 2023.05.21
boj 25682 체스판 다시 칠하기 2  (0) 2023.02.26

https://www.acmicpc.net/problem/12841

 

12841번: 정보대 등산

숭실 대학교 정보 과학관은 숭실 대학교 건물 중 제일 높은 곳에 있다. 민주는 평소에 버스를 타고 이 언덕을 오르지만, 이 문제에 등장하기 위하여 오늘 하루만 걸어서 올라간다. 정보 과학관을

www.acmicpc.net

출발 지점은 왼쪽, 도착 지점은 오른쪽에 있으므로 무조건 횡단보도를 건너야 합니다. 

문제에서는 1번만 횡단보도를 건널 수 있다고 제한하고 있습니다.

그렇게 되면 계산은 간단해집니다.

왼쪽 길로 가다가 횡단보도를 건너고 나머지는 오른쪽 길로만 간다는 뜻이 됩니다.

 

여기서 누적 합을 떠올릴 수 있습니다.

왼쪽, 오른쪽 길의 누적합을 각각 구합니다.

아래 코드에서는 i + 1번 지점까지의 거리를 dp[i]로 저장하고 있습니다.

따라서 i번 지점에서 횡단보도를 건너려면 dp[i - 1] 까지만 계산하면 됩니다.

dp[i - 1].first + cross[i]: 왼쪽에서 i번 지점까지 이동 후 횡단보도를 건넜을 때의 길이가 됩니다.

 

횡단보도를 건넜으니 이제 오른쪽 길에 위치해 있습니다.

따라서 N번 지점까지 그냥 가기만 하면 됩니다. (+ dp[N - 1].second - dp[i - 1].second)

 

거리가 같으면 번호가 낮은 지점을 출력해야 한다는 점만 주의하셔서 최소를 갱신해주시면 됩니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#define MAX 100001
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
 
pii dp[MAX];
ll cross[MAX];
int N;
 
void func() {
    int idx = 0;
    ll ret = 1e12;
    for (int i = 1; i <= N; i++) {
        ll sum = cross[i] + dp[i - 1].first + dp[N - 1].second - dp[i - 1].second;
        if (ret > sum) {
            idx = i;
            ret = sum;
        }
    }
 
    cout << idx << ' ' << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> cross[i];
    }
 
    for (int i = 1; i < N; i++) {
        cin >> dp[i].first;
        dp[i].first += dp[i - 1].first;
    }
 
    for (int i = 1; i < N; i++) {
        cin >> dp[i].second;
        dp[i].second += dp[i - 1].second;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 11560 다항식 게임  (0) 2024.06.13
boj 28018 시간이 겹칠까?  (0) 2023.08.08
boj 25427 DKSH를 찾아라  (0) 2023.05.21
boj 25682 체스판 다시 칠하기 2  (0) 2023.02.26
boj 12996 Acka  (0) 2023.01.29

https://www.acmicpc.net/problem/15926

 

15926번: 현욱은 괄호왕이야!!

첫 번째 입출력에서, 맨 처음 위치부터 4개를 잘라낸 (())가 가장 긴 올바른 괄호 문자열이다. 두 번째 입출력에서, 6번째 위치부터 8개를 잘라낸 ()((()))가 가장 긴 올바른 괄호 문자열이다.

www.acmicpc.net

주어진 입력에서 올바른 괄호쌍의 부분 문자열이 가장 긴 길이를 구하는 문제입니다.

올바른 괄호쌍을 구하기 위해서는 stack을 이용합니다.

 

기본 스택문제와 동일하게 `(`가 나오면 stack에 push, `)`가 나오면 stack에서 pop 연산을 수행합니다.

이 문제는 주어진 문자열의 인덱스를 이용합니다.

`(`가 나오면 그 인덱스를 stack에 push합니다.

`)`가 나오면 s.top의 인덱스와 현재 인덱스에 true 값을 넣습니다.

 

최종으로는 chk[i] = true인 부분의 max 길이를 구해주시면 되겠습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
#define MAX 200001
using namespace std;
 
string str;
bool chk[MAX];
int N;
 
void func() {
    stack<int> s;
    for (int i = 0; i < N; i++) {
        if (str[i] == '(') {
            s.push(i);
        }
        else {
            if (s.empty()) continue;
 
            chk[i] = chk[s.top()] = true;
            s.pop();
        }
    }
 
    int ret = 0;
    int conn = chk[0];
    for (int i = 1; i < N; i++) {
        if (chk[i]) conn++;
        else conn = 0;
 
        ret = max(ret, conn);
    }
 
    cout << ret << '\n';
}
 
void input() {
    cin >> N >> str;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 29721 변형 체스 놀이 : 다바바(Dabbaba)  (2) 2025.02.14
boj 21939 문제 추천 시스템 Version 1  (0) 2022.02.11
boj 17299 오등큰수  (0) 2021.02.22
boj 9372 상근이의 여행  (0) 2021.02.09
boj 1158 요세푸스 문제  (0) 2021.02.09

https://www.acmicpc.net/problem/25427

 

25427번: DKSH를 찾아라

준혁이는 DKSH(단국대학교부속소프트웨어고등학교)에 다니는 학생이다. 어느 날, 준혁이는 길을 걷다가 $N$ 개의 알파벳 대문자가 써있는 종이를 발견했다. 평소에 자신이 DKSH에 다니는 학생이라

www.acmicpc.net

 

4개의 문자를 제외하고 모두 제거했을 때, 남은 문자열이 DKSH일 경우의 수를 구하는 문제입니다.

DKSH의 순서를 유지해야 하며, (a < b < c < d) 조건을 만족하는 (a, b, c, d) 쌍의 갯수를 구해야 합니다.

dp[idx][pos]: list의 idx번째 문자, DKSH 중 pos번쨰 문자를 확인할 때 "DKSH"를 만들 수 있는 경우의 수

 

우선 가장먼저 떠오른 방법이 재귀입니다.

pos == 4, 즉 DKSH를 모두 찾았다면 1을 리턴합니다.

DKSH를 모두 찾지 못했는데 list 내의 문자열을 모두 확인했다면 0을 리턴합니다.

모든 인덱스에 대해 해당 문자를 고르지 않고 idx + 1, pos번째 문자를 확인할 수 있습니다.

그리고 현재 idx번째 문자와 pos번째 문자가 일치하면 idx + 1, pos + 1번째 문자를 확인합니다.

두 가지의 경우를 모두 더해주시면 답이 되겠습니다.

 

여기까지 제가 생각했던 방법이고, 이 방법을 사용하지 않은 풀이도 존재합니다.

어떤 인덱스 idx를 기준으로 경우의 수를 조합하는 방법으로는

idx의 왼쪽에서 해당되는 문자의 갯수 * idx의 오른쪽에 해당되는 문자의 갯수로 구할 수 있습니다.

 

예시로 "YYYSSS"라는 문자열로 "YS"를 만들 수 있는 경우의 수는

왼쪽의 Y1 Y2 Y3 (3개) * 오른쪽의 S1 S2 S3 (3개) = 9로 구할 수 있습니다.

이를 변형해서 Y1 (S1 S2 S3) + Y2 (S1 S2 S3) + Y3 (S1 S2 S3)로도 구할 수 있으며, 이 문제는 이 방법을 이용합니다.

이 방법을 이용하여 해결할 수 있습니다.

찾은 문자에 대해서 왼쪽에 pos-1번 문자의 카운팅이 몇번 진행되었는지 확인만 해주면 됩니다.

'D'를 찾았다면 첫번째 문자이므로 d에 1을 더합니다.

'K'를 찾았다면 앞에 'D'가 카운팅 된 d를 k에 더해줍니다.

'S'를 찾았다면 앞에 'K'가 카운팅 된 k를 s에 더해줍니다.

'H'를 찾았다면 앞에 'S'가 카운팅 된 s를 h에 더해줍니다.

출력은 h를 해주시면 됩니다.

 

첫번째 방법
두번째 방법

역시 두번째 방법이 O(N)으로 끝나기 때문에 속도가 더 빠름을 알 수 있습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    private final static int MAX = 100000;
    private final static char pat[] = new char[]{'D', 'K', 'S', 'H'};
    private static char[] list;
    private static long dp[][] = new long[MAX][4];
    private static int N;
 
    private static long solve(int idx, int pos) {
        if (pos == 4) return 1;
        if (idx == N) return 0;
        if (dp[idx][pos] != -1) return dp[idx][pos];
        dp[idx][pos] = solve(idx + 1, pos);
 
        if (list[idx] == pat[pos]) {
            dp[idx][pos] += solve(idx + 1, pos + 1);
        }
 
        return dp[idx][pos];
    }
 
    private static void init() {
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], -1);
        }
    }
 
    private static void func() {
        init();
        System.out.println(solve(0, 0));
    }
 
    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        list = st.nextToken().toCharArray();
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 
 cs

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    private static char[] list;
    private static int N;
 
    private static void func() {
        long d = 0;
        long k = 0;
        long s = 0;
        long h = 0;
        for (int i = 0; i < N; i++) {
            if (list[i] == 'D') d++;
            else if (list[i] == 'K') k += d;
            else if (list[i] == 'S') s += k;
            else if (list[i] == 'H') h += s;
        }
 
        System.out.println(h);
    }
 
    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        list = st.nextToken().toCharArray();
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 
 cs

'algorithm > dp' 카테고리의 다른 글

boj 28018 시간이 겹칠까?  (0) 2023.08.08
boj 12841 정보대 등산  (0) 2023.07.31
boj 25682 체스판 다시 칠하기 2  (0) 2023.02.26
boj 12996 Acka  (0) 2023.01.29
boj 14450 Hoof, Paper, Scissors (Gold)  (0) 2022.12.30

https://www.acmicpc.net/problem/1456

 

1456번: 거의 소수

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

www.acmicpc.net

정수론 문제는 처음이네요?

 

이 문제에서 요구하는 거의 소수란, 어떤 소수의 N제곱(N >= 2) 꼴이 되는 수라고 합니다.

즉, 8은 2의 3제곱이므로 거의 소수이며, 1024는 2의 10제곱이므로 거의 소수가 됩니다.

주어지는 [A ~ B]의 구간에서 거의 소수의 갯수를 구하는 문제입니다.

 

먼저 소수를 알아야하므로 에라토스테네스의 체로 소수를 모두 구합니다.

범위가 10^14까지인데, 어떤 소수의 제곱이 10^14이하가 되는거라 10^7까지의 소수만 구하도록 합니다.

 

그리고 2부터 1씩 증가하면서 i가 소수인지 확인을 합니다.

소수가 맞다면 i의 n제곱이 r이하일 동안에는 계속 i를 곱해줍니다.

이 과정에서 l 이상, r 이하일 동안은 카운팅을 진행합니다.

어차피 소수 i의 n제곱이고, 그 수는 다른 소수를 곱해서는 도달할 수 없는 수입니다.

 

이 과정에서 문제가 있었습니다.

i를 계속 곱하는 과정에서 수가 long 범위를 벗어나는 경우입니다.

어떤 소수를 n제곱 하면 long 범위를 초과했고, 음수 값이 되어 r을 넘는 값임에도 계속 반복문을 도는 문제가 있었습니다.

 

결국에는 WA를 받게되었고, i를 1번 덜 곱하는 방법으로 해결하였습니다.

i * i <= r 이라는 식을 i <= r / i 로 변경하여 곱셈을 진행하였고, 이 방법으로는 long 범위를 초과하지 않는다는 것을 확인했습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    private final static int MAX = 10000001;
    private static boolean prime[] = new boolean[MAX];
    private static long l, r;
 
    private static void init() {
        for (int i = 2; i * i < MAX; i++) {
            if (prime[i]) continue;
 
            for (int j = 2; i * j < MAX; j++) {
                prime[i * j] = true;
            }
        }
    }
 
    private static void func() {
        init();
 
        int ret = 0;
        for (long i = 2; i * i <= r; i++) {
            if (prime[(int) i]) continue;
            long mul = i;
            while (mul <= r / i) {
                mul *= i;
                
                if (mul >= l) {
                    ret++;
                }
            }
        }
 
        System.out.println(ret);
    }
 
    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        l = Long.parseLong(st.nextToken());
        r = Long.parseLong(st.nextToken());
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 
 cs

https://www.acmicpc.net/problem/27977

 

27977번: 킥보드로 등교하기

첫 번째 줄에 학교까지의 거리, 킥보드 충전소의 개수, 최대 충전소 방문 횟수를 나타내는 세 정수 $L, N, K$가 공백으로 구분되어 주어진다. 두 번째 줄에 $i$번째 충전소의 위치를 나타내는 $N$개

www.acmicpc.net

지인분이 출제한 대회문제가 백준에 등록되었습니다.

문제출제라니.. 무슨 문제를 만들어야하고, 테케는 어떻게 만드는지 모르는 입장에서 그저 신기하네요 ㅋㅋㅋ

다행히 제가 풀수있는 문제를 만들어 주셨습니다 ㅎㅎ

 

이 문제는 0에서 출발하여 L까지 정해진 배터리 용량으로 목적지까지 가야합니다.

충전소는 N개, A[i] 지점마다 있으며, 최대 K번 충전이 가능합니다.

이 때 최초 구매할 수 있는 배터리 용량의 최소를 구하는 문제입니다.

 

최종으로 구해야 하는건 배터리 용량의 최소이므로 이를 파라매트릭 서치로 구해야 합니다.

목적지까지는 갈 수 있어야하므로 최소 용량 l은 maxDis가 되겠고, 최대 용량 r은 출발지점에서 목적지까지의 거리 L이 되겠습니다.

maxDis는 출발지점과 첫 번째 충전소, 각 인접한 충전소들, 마지막 충전소와 도착지점 사이의 거리의 최대입니다.

그리고 계산의 편의를 위해 배열에 도착지점인 L을 추가합니다.

이 문제는 충전소의 위치가 정렬된 상태로 주어지므로 정렬로직이 필요 없습니다.

 

그러면 배터리 용량이 m이라고 했을 때, 충전소를 K번 이하 방문하면서 목적지점인 L 까지 갈 수 있는지 확인합니다.

L에 도착했을 때 충전소를 K번 이하로 방문할 수 있다면 ret을 갱신하고 범위를 작게 맞춰서 최적 해를 구합니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <algorithm>
#define MAX_N 100001
using namespace std;
 
int list[MAX_N];
int L, N, K, maxDis;
 
void func() {
    int l = maxDis;
    int r = L;
 
    int ret = 0;
    while (l <= r) {
        int m = (l + r) / 2;
 
        int now = m;
        int pos = 0;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (list[i] - pos > now) {
                cnt++;
                now = m;
            }
            now -= (list[i] - pos);
            pos = list[i];
        }
 
        if (cnt <= K) {
            ret = m;
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }
 
    cout << ret << '\n';
}
 
void input() {
    cin >> L >> N >> K;
 
    int pre = 0;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
        maxDis = max(maxDis, list[i] - pre);
        pre = list[i];
    }
    maxDis = max(maxDis, L - pre);
    list[N++] = L;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

'algorithm > binarysearch' 카테고리의 다른 글

boj 18113 그르다 김가놈  (0) 2022.10.09
boj 2295 세 수의 합  (0) 2022.06.28
boj 2110 공유기 설치  (0) 2021.04.13
boj 7453 합이 0인 네 정수  (0) 2021.01.22
boj 2143 두 배열의 합  (0) 2021.01.22

https://www.acmicpc.net/problem/25682

 

25682번: 체스판 다시 칠하기 2

첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

www.acmicpc.net

2차원 배열 내 누적합 문제입니다.

2차원 누적합은 (sx, sy) ~ (ex, ey)의 누적합을 말하며, dp[i][j] = cur + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] 공식을 활용해야 합니다.

 

체스판은 검은색, 흰색이 번갈아 칠해져있어야 하고, (1, 1) 지점의 색은 정해지지 않았습니다.

따라서 (1, 1) 지점에 검은색이 올 경우와 흰색이 올 경우를 모두 구해서 최솟값을 구해야 합니다.

이를 위해 dp를 두개 사용합니다.

 

좌표의 x, y값을 더한 값이 홀수인 좌표들끼리와 짝수인 좌표들끼리의 색은 같습니다.

이를 활용하여 해당 좌표에 색이 바껴야하는지에 대해서 각각 누적합을 구할 수 있습니다.

dp를 채웠다면 K * K 크기의 정사각형의 누적합들을 순회하며 최솟값을 구하도록 합니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <algorithm>
#define MAX 2001
using namespace std;
 
char list[MAX][MAX];
int bdp[MAX][MAX], wdp[MAX][MAX];
int N, M, K;
 
void getPrefixSum() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            bdp[i][j] = bdp[i - 1][j] + bdp[i][j - 1] - bdp[i - 1][j - 1];
            wdp[i][j] = wdp[i - 1][j] + wdp[i][j - 1] - wdp[i - 1][j - 1];
 
            if (list[i][j] == 'W') {
                if ((i + j) % 2) {
                    wdp[i][j]++;
                }
                else {
                    bdp[i][j]++;
                }
            }
            else {
                if ((i + j) % 2) {
                    bdp[i][j]++;
                }
                else {
                    wdp[i][j]++;
                }
            }
        }
    }
}
 
void func() {
    getPrefixSum();
    int ret = 2147483647;
    for (int i = K; i <= N; i++) {
        for (int j = K; j <= M; j++) {
            ret = min(ret, bdp[i][j] - bdp[i - K][j] - bdp[i][j - K] + bdp[i - K][j - K]);
            ret = min(ret, wdp[i][j] - wdp[i - K][j] - wdp[i][j - K] + wdp[i - K][j - K]);
        }
    }
 
    cout << ret << '\n';
}
 
void input() {
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 12841 정보대 등산  (0) 2023.07.31
boj 25427 DKSH를 찾아라  (0) 2023.05.21
boj 12996 Acka  (0) 2023.01.29
boj 14450 Hoof, Paper, Scissors (Gold)  (0) 2022.12.30
boj 14453 Hoof, Paper, Scissors (Silver)  (0) 2022.12.30

+ Recent posts

티스토리툴바