문제
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.
즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)
둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)
출력
첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.
풀이
코드 구현은 짧은데 로직이 어렵다 ㅜ-ㅜ
부분 구간의 시작 인덱스를 i, 끝 인덱스를 j라 하자.
연속된 부분 구간의 합이 M으로 나누어떨어지기 위해서는
(prefix_sum[j] - prefix_sum[i - 1]) % M = 0 이어야 하므로
prefix_sum[j] % M = prefix_sum[i - 1] % M 일 경우, i ~ j 구간의 합이 M으로 나누어떨어진다.
따라서 i와 j의 조합 수를 구하여 모두 더하면, 답을 구할 수 있다.
아래 그림에 각 인덱스에 따른 prefix sum을 나타내보았다.
해당 인덱스를 j라고 생각하고, (i, j)를 구해 보면
j
0 : X
1 : X
2 : (1, 2)
3 : (1, 3), (3, 3)
4 : (2, 4)
5 : (1, 5), (3, 5), (4, 5)
총 7개가 나온다.
prefix_sum[j] / M == 0 일 경우, 처음부터 j까지의 부분은 무조건 나누어 떨어지므로, 계산의 편의를 위해 input를 0번째가 아닌 1번째부터 받았다.
input을 받는 동시에, prefix_sum % M을 하고, remainder_count[prefix_sum % M]를 1씩 늘려 주면, prefix_sum % M이 각각 몇 개씩 나왔는지 알 수 있다.
마지막에 remainder_count[]의 모든 인덱스를 index C 2 하여 더하면 끝 !
코드
#include <iostream>
using namespace std;
long long n, m, sum, result;
long long remainder_count[1001];
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
int i = -1;
while (++i < n)
{
long long input;
cin >> input;
sum += input;
remainder_count[sum % m]++;
}
remainder_count[0]++;
i = -1;
while (++i < 1001)
result += remainder_count[i] * (remainder_count[i] - 1) / 2;
cout << result << '\n';
return (0);
}
main 내에서 int sum만 해놓고 0으로 초기화를 안 해서 자꾸 틀렸다..... 근데 테스트케이스는 왜 잘 나왔는지 모르겠다. 컴파일러 차이인가 ㅜ-ㅜ
어쨌든 성공 !
