[C/C++] 백준 10986번 - 나머지 합

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;

int N, M, x;
long long cnt[1001];
long long sum, ans;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		cin >> x;
		sum += x;
		cnt[sum % M]++;
	}

	for (int i = 0; i <= 1000; i++)
	{
		ans += cnt[i] * (cnt[i] - 1) / 2;
	}
	
	cout << cnt[0] + ans;
}

 

풀이 방법

수열을 S 누적합의 배열을 PrefixSum이라 한다면 S[i+1]번째부터 S[j]까지의 구간합은 PrefixSum[j] - PrefixSum[i]이다.

문제에서는 (PrefixSum[j] - PrefixSum[i] ) % MOD = 0이 되는 i, j의 쌍을 구하는 것을 요구하고 있다.

모듈러 연산에 의해  

(PrefixSum[j] - PrefixSum[i] ) % MOD = 0 이 만족한다면

PrefixSum[j] % MOD = PrefixSum[i] % MOD 도 만족하게 된다.

 

예제 입력 1과 같이 입력이 주어질 때

5 3
1 2 3 1 2

 

 

index	1	2	3	4	5
S	1	2	3	1	2

index	0	1	2	3	4	5
prefix_sum	0	1	3	6	7	9

 

예를 들어 prefix_sum[4] - prefix_sum[1] 는 S[2] + S[3] + S[4] = 6을 의미하게 된다. 

 

여기에서 prefix_sum(누적합)들을 모듈러 연산을 해주면 아래와 같이 나오는데, 

index	1	2	3	4	5
prefix_sum%MOD	1	0	0	1	0

 

아까 위에서 봤던 것처럼 PrefixSum[j] % MOD = PrefixSum[i] % MOD 인 것들의 쌍을 구해보면

1 - 1 인 (1, 4)

0 - 0 인 (2, 3), (2, 5), (3, 5)로 총 4개가 나오게 된다.

그리고 prefix_sum%MOD = 0 이 되는 것들의 의미는 첫 번째 원소부터 i번째까지의 누적합이 MOD로 나누어 떨어진다는 의미기 때문에 (0, 2), (0, 3), (0, 5)로 3개가 더 추가된다(prefix_sum% MOD = 0인 개수)

따라서 답은 7이 된다.

 

 

www.acmicpc.net/problem/10986

10986번: 나머지 합