[백준/C++] 10986번 : 나머지 합 (누적 합)

나머지 합

문제

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10^6, 2 ≤ M ≤ 10^3)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 10^9)

출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

예제 입력 1

5 3
1 2 3 1 2

예제 출력 1

7

---

해당 문제는 누적합 알고리즘을 이용해 풀이하는 문제이다.

 

❌ 첫번째 풀이 방법 - 시간초과

#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

	int N, M;
	cin >> N >> M;
	vector<int> arr(N+1);
	int cnt = 0;

	for(int i = 1; i <= N; i++)
	{
		int temp;
		cin >> temp;
		arr[i] = arr[i - 1] + temp;
		if (arr[i] % M == 0)
			cnt++;
		for (int j = 1; j <= i - 1; j++)
		{
			if ((arr[i] - arr[j]) % M == 0)
				cnt++;
		}
	}
	cout << cnt;

	return 0;
}

첫번째 방법으로는 누적되는 배열의 합을 arr 배열에 저장한 뒤, 2중 for문을 돌면서 구간합을 M으로 나눠 찾는 것이다.

결과는 시간초과로 인한 실패였다.

 

N의 범위가 1부터 10의 6승이기 때문에 2중 for문을 돌 때 제한시간 1초를 초과하게 된다.

 

따라서 2중 for문이 아닌 1중 for문으로 문제를 해결해야 했는데, 아무리 고민해봐도 정답이 떠오르지 않아 정답을 참고하였다.

---

나머지를 구하는 모듈러 연산자(%)를 사용하는 부분을 자세히 보자.

(arr[i] - arr[j]) % M == 0 

모듈러 연산자(줄여서 mod)는 분배법칙이 성립하여 (arr[i] - arr[j]) % M == 0  이 만족한다면, (arr[i] % M) - (arr[j] % M) == 0 도 만족하고, 항을 넘겨 arr[i]%M == arr[j] % M 도 만족하게 된다.

 

즉, (arr[i] - arr[j]) % M == 0 는 arr[i] % M = arr[j] % M 과 같다.

 

이러한 공식에 따라서 나누기의 결과가 같은 두 쌍이 얼마나 존재하는지를 구하는 것이 이 문제의 핵심이었다.

 

첫번째 풀이에서 작성했던 if ((arr[i] - arr[j]) % M == 0) cnt++; 소스코드를 cnt += (두 쌍의 조합 개수) 로 변경하면 1중 for문으로도 문제를 풀이할 수 있는것이다.

 

⭕ 두번째 풀이방법 - 성공

#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

	int N, M;
	cin >> N >> M;
	
	vector<long long> v(1001);
	long long cnt = 0;
	long long sum = 0;
	for(int i = 0; i < N; i++)
	{
		int temp;
		cin >> temp;
		sum += temp;
		v[sum % M]++;
	}

	for(int i = 0; i < v.size(); i++)
		cnt += v[i] * (v[i] - 1) / 2; // nC2
	
	cout << cnt + v[0];

	return 0;
}

 

누적합을 더하면서, 해당 합이 M으로 나누어지는 나머지 값을 인덱스로 하여 벡터를 1씩 더해주었다.

즉, 나머지가 0인 결과가 3번 나오면 v[0] = 3 이 되는것이고, 나머지가 2인 결과가 1번 나오면 v[1] = 1 이 되는것이다.

 

두 쌍의 개수를 구하는 방법은 nC2 와 같은 조합 공식을 이용하면 된다. 

조합 (Combination) 공식은 n * n-1 / 2 이므로, 이를 이용해 v[i] * (v[i] - 1 ) / 2 의 결과를 cnt 결과 카운팅 변수에 더해주었다.

 

이때 첫번째 함정은, 마지막 cnt를 출력할 때 v[0] 의 개수를 더해서 출력해야 한다.

나머지가 0인 v[0]에 해당하는 원소들은 첫번째 원소부터 i번째까지 누적합이 모두 mod로 나누어 떨어진다는 의미이기 때문에 (0, 2), (0, 3), (0, 5)같은 쌍이 또 추가되기 때문이다.

 

두번째 함정은, N과 M의 범위가 크기 때문에 변수들의 자료형을 long long형으로 선언해야 한다는 점이다.

처음엔 int 형으로 선언해 풀었는데 모든 풀이가 맞더라도 1% 에서 탈락하는 결과를 보였다.

 

여러모로 매우 어려운 문제였다..

---

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

10986번: 나머지 합

https://cocoon1787.tistory.com/396

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