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

단계별로 풀어보기 17단계(누적 합) 4번 문제

https://www.acmicpc.net/step/48

누적 합 단계

---

백준 10986번: 나머지 합

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

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으로 나누어 떨어지는 구간의 개수를 출력한다.

---

접근 방법

이번 문제는 배열 A의 숫자 개수 N과 나눌 숫자 M을 입력받고 N개의 숫자를 입력해서 해당 숫자들을 연속해서 더 했을 때 M으로 나누어 떨어지는 구간 개수를 출력하는 문제다.

1	2	3	1	2
1	2	3	1	2
1	2	3	1	2
1	2	3	1	2
1	2	3	1	2
1	2	3	1	2
1	2	3	1	2

예제를 통해서 보면 위 표처럼 [1, 2], [1, 2, 3], [1, 2, 3, 1, 2], [2, 3, 1], [3], [3, 1, 2], [1, 2]의 연속되는 구간 7개가 3으로 나누어 떨어지므로  7이 출력되는 것이다.

우선 위 표를 보고 간단하게 생각하면 누적 합을 이용해서 처음부터 계속 누적해가면서 M으로 나눈 나머지가 0인 것의 개수만 세면 되는 것 처럼 보인다.

하지만 그렇게 하면 앞의 [1, 2], [1, 2, 3], [1, 2, 3, 1, 2]의 연산만 해서 3을 출력하게 될 것이다.

이를 위해서 추가적으로 nC2, 그러니까 조합 연산이 추가되어야 한다.

개인적으로 이 마지막 조합 연산 부분을 생각하지 못해 막혀서 여러 블로그들을 참고해서 문제 풀이를 진행했다. 역시 수학은 힘들다..

---

코드

#include <iostream>
using namespace std;
#define MAX 1000001

long long A[MAX];
long long sum[MAX];

int main(int argc, char * argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	long long count = 0;
	int N, M;
	cin >> N >> M;

	sum[0] = 0;
	for (int i = 1; i <= N; i++) {
		int num;
		cin >> num;

		sum[i] = (sum[i - 1] + num) % M;
		if (sum[i] == 0)
			count++;

		A[sum[i]]++;
	}

	for (int i = 0; i < M; i++)
		count += A[i] * (A[i] - 1) / 2;

	cout << count << endl;

	return 0;
}

---

결과

백준 제출 결과

배열 크기만이 아닌 입력되는 값도 10^6이라서 int를 쓰면 안되는데 썼다가 틀렸다.