https://www.acmicpc.net/problem/3673
3673번: 나눌 수 있는 부분 수열
양의 정수로 이루어진 수열이 주어졌을 때, 연속하는 부분 수열의 합이 d로 나누어 떨어지는 것의 개수를 구하는 프로그램을 작성하시오. 예를 들어, 아래와 같은 수열의 부분 수열 중 4로 나누
www.acmicpc.net
M으로 나누어 떨어지는 연속하는 부분 수열의 합의 갯수를 찾는 문제입니다.
이 문제의 키워드는 "연속" 이며, 누적 합을 이용합니다.
|
1
2
|
M = 4, N = 8
2 1 2 1 1 2 1 2
|
cs |
위의 입력을 예시로 우선 수열의 누적합을 구해 각각의 MOD M을 구합니다.
|
1
2
|
sum = 2 3 5 6 7 9 10 12
MOD M = 2 3 1 2 3 1 2 0
|
cs |
그러면 위와 같이 누적 합과 누적 합의 MOD M 값을 카운팅합니다.
M = 4이므로
나머지가 0인 갯수는 1
나머지가 1인 갯수는 2
나머지가 2인 갯수는 3
나머지가 3인 갯수는 2
이렇게 됩니다.
여기서 나머지가 1인 부분 수열을 설명하면
sum(1 ~ 3), sum(1 ~ 6)의 나머지가 1로 같다는 말입니다.
그러면 sum(4 ~ 6)의 나머지는 0이라는 말이 됩니다.
따라서 나머지가 같은 부분 수열에서 2개를 뽑는 조합을 구하면 되는 겁니다.
나머지가 1인 부분 수열은 2개이므로 2개 중에 2개를 뽑는 경우의 수: 1
나머지가 2인 부분 수열은
sum(1 ~ 1), sum(1 ~ 4), sum(1 ~ 7)로 3개로
3개 중에 2개를 뽑는 경우의 수로 3이라는 답이 나옵니다.
같은 방식으로 나머지가 0 ~ M - 1일 때의 경우의 수를 모두 구해줍니다.
|
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
|
#include <iostream>
#include <cstring>
#define MAX_N 50001
#define MAX_M 1000000
using namespace std;
typedef long long ll;
ll dp[MAX_N], cnt[MAX_M];
int N, M;
void func() {
ll ans = cnt[0];
for (int i = 0; i < M; i++) {
if (cnt[i] < 2) continue;
ans += ((cnt[i] * (cnt[i] - 1)) / 2LL);
}
cout << ans << '\n';
}
void input() {
cin >> M >> N;
for (int i = 1; i <= N; i++) {
cin >> dp[i];
dp[i] += dp[i - 1];
cnt[dp[i] % M]++;
}
}
void init() {
memset(cnt, 0, sizeof(cnt));
}
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 > dp' 카테고리의 다른 글
| boj 10986 나머지 합 (0) | 2022.03.08 |
|---|---|
| boj 14238 출근 기록 (0) | 2022.02.04 |
| boj 20500 Ezreal 여눈부터 가네 ㅈㅈ (0) | 2022.01.01 |
| boj 1135 뉴스 전하기 (0) | 2021.11.15 |
| boj 17090 미로 탈출하기 (0) | 2021.06.27 |