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

 

생애 첫 루비문제입니다.

애드혹 문제라서 그런지 백준 게시판이나 블로그에서 아이디어를 얻지 않았다면 절대 손도 못댈거같은 그런 문제였습니다..

 

제가 힌트를 얻은건 1 ~ N번째 수를 계속 이어붙였을 때 음수 누적합이 나오는 갯수를 구하는 것이었습니다.

사실상 문제의 모든것 이었습니다..

 

아무튼 저는 누적합으로 접근했고, 각 은행들은 원형으로 배치되어 있기때문에 1 ~ N이 아닌 1 ~ 2N의 누적합으로 구해줍니다.

그리고 1, 2, 3, ... N에서 시작하여 N개의 수를 계속 이어붙일 때의 누적합들 중에 음수가 몇번 나오는지 카운팅하면 그게 답입니다.

 

4
1 -2 -1 3

예시로 설명드리면

처음 1번부터 누적합을 쭉 구하면

1 -1 -2 1 / 2 0 -1 2 / 3 1 0 3

이렇게 되고, 음수의 갯수는 3개입니다.

그리고 이후에 배열을 계속 이어도 음수가 나오지 않습니다.

 

그 다음 2번부터 누적합을 구하면

x -2 -3 0 1 / -1 -2 1 2 / 0 -1 2 3

이렇게 되고, 음수의 갯수는 5개입니다.

 

다음 3번부터 누적합을 구하면

x x -1 2 3 1 / 0 3 4 2 / 1 4 5 3

이렇게 되고, 음수의 갯수는 1개입니다.

 

마지막 4번부터 누적합을 구하면

x x x 3 4 2 1 / 4 5 3 2 / 5 6 4 3

이렇게 되고, 음수의 갯수는 0개입니다.

위에서 구한 갯수들을 전부 더하면 9개가 됩니다.

 

이 과정에서 규칙을 하나 찾을 수 있습니다.

우선 문제에서 입력으로 주어지는 수를 모두 더하면 양수라고 했습니다.

그리고 각 시작 지점을 i번이라고 했을 때 i번부터 N개의 누적합은 무조건 양수입니다.

 

제가 4개씩 끊은 구간들을 보시면 1번 구간의 수들에서 +1한 값들이 2번 구간이 되어 있습니다.

그리고 2번 구간에서 +1를 하면 3번 구간이 됩니다.

그 +1은 배열의 전체 누적합이 되고, 음수의 갯수는 음수 누적합 / 전체 누적합이 되는것을 알 수 있습니다.

계산하면 실수가 나오기 때문에 double형으로 바꿔주셔야 하고, 나머지는 무조건 올림 연산을 해야합니다.

이 방식으로 접근하시면 로직 자체는 간단하게 구현하실 수 있습니다.

이 문제는 이 방식을 생각해내는것 자체가 정말 어렵다는 것을 느꼈습니다.

 

 

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 <cmath>
#define MAX 20001
using namespace std;
typedef long long ll;
 
int dp[MAX];
int N;
 
void init() {
    for (int i = 1; i <= (N << 1); i++) {
        dp[i] += dp[i - 1];
    }
}
 
void func() {
    init();
 
    ll ret = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = i; j < N + i; j++) {
            if (dp[j] - dp[i - 1] >= 0) continue;
            ret += (ll)ceil((double)(-dp[j] + dp[i - 1]) / (double)(dp[N + i - 1] - dp[i - 1]));
        }
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> dp[i];
        dp[i + N] = dp[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 14370 전화번호 수수께끼 (Large)  (0) 2024.08.06
boj 21316 스피카  (0) 2024.08.05
boj 5527 전구 장식  (0) 2024.07.30
boj 14864 줄서기  (0) 2024.07.26
boj 2381 최대 거리  (0) 2024.07.25

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

 

점화식만 구한다면 쉽게 풀리는 문제입니다.

2차원 배열의 누적합이지만 기존 방식처럼 (1, 1) ~ (x, y)의 모든 값을 더하는 것이 아닌 대각선 범위에 있는 수들을 더해야합니다.

 

우선 본인보다 위에 있는 수는 포함되어야 합니다. 그러면 dp[i - 1][j]를 추가합니다.

다음은 본인보다 대각선 위에 있는 수도 포함되어야 합니다. 그러면 dp[i - 1][j - 1]가 추가됩니다.

 

여기서 하나 생각해야할건 dp[i - 1][j]에는 dp[i - 2][j - 1]이 포함되어 있습니다. (대각선)

그리고 dp[i - 1][j - 1]에도 dp[i - 2][j - 1]가 포함되어 있습니다. (위)

그러니 i > 1인 좌표에서는 dp[i - 2][j - 1]를 한번 빼줘야 점화식이 완성됩니다.

 

그러면 최종 점화식은

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

이렇게 됩니다!

점화식을 구했으니 이제 입력이 들어오면 바로 dp[x][y]를 출력해주시면 되겠습니다.

 

 

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>
#define MAX 2001
using namespace std;
 
int dp[MAX][MAX];
int N, M, Q;
 
void func() {
    int x, y;
    while (Q--) {
        cin >> x >> y;
        cout << dp[x][y] << '\n';
    }
}
 
void input() {
    cin >> N >> M >> Q;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> dp[i][j];
            dp[i][j] += (dp[i - 1][j] + dp[i - 1][j - 1]);
            if (i > 1) {
                dp[i][j] -= dp[i - 2][j - 1];
            }
        }
    }
}
 
int main() {
    cin.tie(nullptr); cout.tie(nullptr);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 19623 회의실 배정 4  (0) 2024.07.29
boj 17258 인기가 넘쳐흘러  (0) 2024.07.20
boj 1398 동전 문제  (0) 2024.07.04
boj 1229 육각수  (0) 2024.06.30
boj 25378 조약돌  (0) 2024.06.29

문제

 

풀이

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

이 문제와 같은 풀이입니다.

 

엘리스는 강림제에 참여한 신도들이 T명 이상 모여야 지상에 강림한다고 합니다.

만약 신도들이 T명 미만으로 모였을 때 친구를 최대 K명까지 초대하여 T명을 맞출 수도 있습니다.

친구들은 친구들을 제외한 신도들이 T명 이상이 되었다면 모두 탈출한다고 하여 적절한 시기에만 친구를 불러야 합니다.

 

저는 dp로 문제에 접근했고, 우선 누적합을 통해 참여하는 신도들의 수를 시간별로 구합니다.

범위로 누적합을 구해야하기 때문에 imos 기법을 활용했습니다.

imos 기법으로 범위의 양 끝지점에만 카운팅을 먼저 하고, 마지막에 한번에 누적합을 구할 수 있습니다.

 

dp[N][K][pre]: N 시간에 친구 K명을 부를 수 있고, 이미 참여중인 친구가 pre명일 때 엘리스가 지상으로 강림하는 최대 시간

문제에서 나올 수 있는 경우는 4가지입니다.

1. 신도들만 T명 이상 모였을 경우

2. 신도 + 이미 참여중인 친구들이 T명 이상 모였을 경우

3. 친구들을 더 추가하여 T명을 채울 수 있는 경우

4. 친구들을 추가해도 T명을 채우지 못하는 경우

 

1번의 경우는 엘리스가 강림할 수 있으므로 +1을 하고 다음 시간을 확인합니다.

이미 참여중인 친구들이 있다면 모두 탈출하기 때문에 pre는 0으로 맞춥니다.

 

2번의 경우도 엘리스가 강림할 수 있으므로 +1을 하고 다음 시간을 확인합니다.

친구들을 제외한 시도들이 T보다 적으므로 pre도 그대로 유지합니다.

 

3번의 경우도 엘리스가 강림할 수 있으므로 +1을 하고 다음 시간을 확인합니다.

친구를 tmp명 더 추가합니다. pre는 pre + tmp가 되겠고, k에서도 tmp만큼 빼줍니다.

 

4번의 경우는 엘리스가 강림할 수 없으므로 바로 다음 시간을 확인합니다.

이때 친구들을 더 추가하지 않으며, 이미 참여중인 친구들은 계속 참여하기 때문에 pre를 그대로 유지합니다.

 

코드

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
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 310
using namespace std;
 
int sum[MAX];
int dp[MAX][MAX][MAX];
int N, M, K, T;
 
int solve(int idx, int k, int pre) {
    if (idx > N) return 0;
    int& ret = dp[idx][k][pre];
    if (ret != -1) return ret;
 
    if (sum[idx] + pre >= T) {
        int next = pre;
        if (sum[idx] >= T) next = 0;
        return ret = solve(idx + 1, k, next) + 1;
    }
 
    ret = solve(idx + 1, k, pre);
    int tmp = T - sum[idx] - pre;
    if (k && k >= tmp) {
        ret = max(ret, solve(idx + 1, k - tmp, pre + tmp) + 1);
    }
    return ret;
}
 
void init() {
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i < MAX; i++) {
        sum[i] += sum[i - 1];
    }
}
 
void func() {
    init();
    cout << solve(1, K, 0) << '\n';
}
 
void input() {
    int l, r;
    cin >> N >> M >> K >> T;
    while (M--) {
        cin >> l >> r;
        sum[l]++;
        sum[r]--;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'대회 > elice' 카테고리의 다른 글

엘리스 코드 챌린지 Day 10 계단 카드 뽑기  (0) 2024.07.24
엘리스 코드 챌린지 Day 9 격자 위의 ELICE  (0) 2024.07.24
엘리스 코드 챌린지 Day 7 계기판 조작하기  (0) 2024.07.23
엘리스 코드 챌린지 Day 6 빨간 선과 파란 선  (0) 2024.07.23
엘리스 코드 챌린지 Day 5 수열 복원  (0) 2024.07.22

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/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/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

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

 

2015번: 수들의 합 4

첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로

www.acmicpc.net

N이 20만이므로 모든 부분합을 직접 구할 수는 없습니다.

기존의 누적합 문제에서 부분합을 구하는 식은 dp[r] - dp[l - 1] = K 입니다.

K는 입력으로 주어지기 때문에 식을 변형하면 dp[r] - K = dp[l - 1]이 되고, 이 식으로 문제에 접근합니다.

 

식을 풀어서 설명하면 dp[r](1 ~ r번 요소의 누적합) - K = dp[l - 1](1 ~ l - 1번 요소의 누적합)

이렇게 되는데, l - 1번을 구할 필요는 없습니다. dp[r] - K와 일치하는 값이 몇 번 나왔는지 세어주면 되는겁니다.

이를 계산하기 위해 map을 사용합니다. 정렬이 필요없으므로 unordred_map을 사용하였습니다.

 

누적합을 구하면서 dp[i] - K 값이 map에 있다면 map[dp[i] - K]만큼 카운트를 증가시킵니다.

그리고 dp[i] 값을 새롭게 map에 넣어주거나 1을 증가시킵니다.

dp[i] 값이 K인 경우는 ans를 따로 증가시켜야 합니다.

 

N = 200000, K = 0이고, 배열의 값이 모두 0이라면 int 범위를 넘으므로 long 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
#include <iostream>
#include <unordered_map>
#define MAX 200001
using namespace std;
typedef long long ll;
 
int dp[MAX];
int N, K;
 
void func() {
    unordered_map<int, ll> m;
    ll ans = 0;
    for (int i = 1; i <= N; i++) {
        dp[i] += dp[i - 1];
        if (dp[i] == K) ans++;
 
        if (m.find(dp[i] - K) != m.end()) {
            ans += m[dp[i] - K];
        }
 
        if (m.find(dp[i]) != m.end()) {
            m[dp[i]]++;
        }
        else {
           m.insert({ dp[i], 1LL });
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> dp[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

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

boj 14453 Hoof, Paper, Scissors (Silver)  (0) 2022.12.30
boj 2281 데스노트  (0) 2022.10.08
boj 21923 곡예 비행  (0) 2022.06.10
boj 12978 스크루지 민호 2  (0) 2022.06.08
boj 10986 나머지 합  (0) 2022.03.08

+ Recent posts

티스토리툴바