https://www.acmicpc.net/problem/10986
10986번: 나머지 합
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j)
www.acmicpc.net
[boj 3673 나눌 수 있는 부분 수열] 문제와 같은 풀이 방법입니다.
모든 수열의 누적합을 구해 각각의 누적 합의 %M 값을 사용합니다.
|
1
2
|
5 3
1 2 3 1 2
|
cs |
위의 입력을 예시로 들면
|
1
2
|
sum = 1 3 6 7 9
MOD M = 1 0 0 1 0
|
cs |
이렇게 됩니다. 저는 이번 문제는 dp에 MOD M한 값을 미리 저장해두었고, cnt[dp[i]]으로 카운팅 하였습니다.
M = 3이므로
나머지가 0인 갯수는 3
나머지가 1인 갯수는 2이므로
나머지가 같은 부분 수열에서 2개를 뽑는 조합을 더하는 식으로 구할 수 있습니다.
|
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
|
#include <iostream>
#define MAX_N 1000001
#define MAX_M 1001
using namespace std;
typedef long long ll;
ll cnt[MAX_M], ans;
int dp[MAX_N];
int N, M;
void func() {
ans = cnt[0];
for (int i = 0; i < M; i++) {
ans += (cnt[i] * (cnt[i] - 1) / 2LL);
}
cout << ans << '\n';
}
void input() {
cin >> N >> M;
for (int i = 1; i <= N; i++) {
cin >> dp[i];
dp[i] = (dp[i] + dp[i - 1]) % M;
cnt[dp[i]]++;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 21923 곡예 비행 (0) | 2022.06.10 |
|---|---|
| boj 12978 스크루지 민호 2 (0) | 2022.06.08 |
| boj 14238 출근 기록 (0) | 2022.02.04 |
| boj 3673 나눌 수 있는 부분 수열 (0) | 2022.01.31 |
| boj 20500 Ezreal 여눈부터 가네 ㅈㅈ (0) | 2022.01.01 |