[백준 10986] 나머지 합 (C++)

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

10986번: 나머지 합

문제

---

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

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

 

입력

---

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

둘째 줄에 N개의 수 A₁, A₂, ..., A_N이 주어진다. (0 ≤ A_i ≤ 10⁹)

 

출력

---

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

 

문제 풀이

---

누적합을 이용하는 문제.

배열의 처음부터 끝까지 누적합을 구해 저장한다. i번째 인덱스까지의 합을 M으로 나누었을 때 0이 아니라면 i번째 인덱스까지의 합에서 그 나머지만큼을 빼야 M으로 나누어 떨어진다. 즉, 나머지에 해당하는 값을 가진 인덱스 이후부터 i번째 인덱스까지의 합을 구하면 M으로 나누어 떨어지게 된다. i-1번 인덱스까지 나머지에 해당하는 값을 가진 인덱스의 개수가 나누어 떨어지는 구간의 개수가 된다.

i번째 인덱스까지의 합을 M으로 나누었을 때 나누어떨어지면, 인덱스 0부터 i번째 인덱스까지의 합이 M으로 나누어떨어지게 된다는 뜻이므로 개수에 1을 더한다. i번째 인덱스 이전의 어떤 인덱스가 M으로 나누어 떨어진다면 해당 인덱스+1부터 i번째 인덱스까지의 합이 M으로 나누어 떨어지게 된다. 즉, i번째 인덱스 이전까지 M으로 나누어 떨어지는 인덱스의 개수를 구한 후 1을 더해주면 답을 구할 수 있다.

 

아래는 예제 입력 1에 대한 예시이다.

5 3
1 2 3 1 2

 

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

1은 3으로 나누었을 때 나머지가 1이다.

 

나머지	indexes
0
1	1
2

 

3은 3으로 나누었을 때 나머지가 0이다.

따라서 처음부터 끝까지의 구간이 가능하다.

나머지	indexes
0	2
1	1
2

6은 3으로 나누었을 때 나머지가 0이다. 

나누어 떨어지는 구간의 개수는 이전까지 나머지가 0인 값의 개수 + 1이 된다.

(처음부터 끝까지의 구간, 3부터 3까지의 구간 2개가 존재한다.)

 

나머지	indexes
0	2, 3
1	1
2

 

7은 3으로 나누었을 때 나머지가 1이다.

따라서 처음부터 끝까지의 누적합에서 누적합의 나머지가 1인 구간을 제외해주면 된다. 이 이전까지 나머지가 1인 값의 개수를 구하면 3으로 나누어 떨어지는 구간의 개수이다. ( 벡터 배열에 저장된 인덱스 1 이후부터 4까지 더하면 된다.)

나머지	indexes
0	2, 3
1	1, 4
2

 

9는 3으로 나누었을 때 나머지가 0이다.

나누어 떨어지는 구간의 개수는 이전까지 나머지가 0인 값의 개수 + 1이 된다. 처음부터 끝까지의 구간, 인덱스 3부터 5까지의 구간, 인덱스 4부터 5까지의 구간이 가능하다. 

나머지	indexes
0	2, 3, 5
1	1, 4
2

 

아래는 코드.

코드에서는 벡터 배열에 인덱스들을 저장해놓았지만 개수 count를 저장하는 것이 깔끔할 것이다.

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

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M;
	int num;
	long long answer = 0;
	cin >> N>>M;
	long long* sums = new long long[N + 1];
	vector<int>* v = new vector<int>[M];
	sums[0] = 0;
	for (int i = 1; i < N + 1; i++)
	{
		cin >> num;
		sums[i] = sums[i - 1] % M + num % M;
		sums[i] = sums[i] % M;
		if (sums[i] == 0)
		{
			answer++;
		}
		answer += v[sums[i]].size();
		v[sums[i]].push_back(i);
	}
	cout << answer << "\n";
	return 0;
}