백준 10986: 나머지 합

문제 요약

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

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

문제 분류

• 수학
• 누적 합

문제 풀이

우선 각 입력을 누적시켜 배열에 저장하는데, m으로 나눈 나머지를 저장하여 누적한다.

누적합 알고리즘에 의해 결국 어떠한 구간 [i, j)에 대하여 S[j] - S[i]가 해당 구간의 합이 되는데, 그렇다면 문제에 의한 조건문은 (S[j] - S[i]) % m == 0의 식이 될 것이다.

그러나 여기서 식을 조금 바꾸어서, S[j] % m== S[i] % m의 식으로 바꿀 수 있다. 즉, 배열 S에 m으로 나눈 나머지를 넣게 된다면 S[i] == S[j]의 식이 된다. 결국, S[i]와 S[j] 같은 쌍의 개수를 찾으면 된다.

m으로 나눈 나머지의 개수는 mcnt[]로 세 주었다. S[i]는 새 입력과 S[i - 1]의 합을 m의으로 나눈 나머지로 하고, 결과 개수 cnt에 mcnt[S[i]]를 누적시키고, 개수를 하나 늘리면 된다.

cnt의 값이 int를 넘어서므로 int보다 크게 잡아야한다. in부분에서도 오버플로우를 염려하여 int보다 크게 자료형을 설정했다.

풀이 코드

#include <stdio.h>
#include <iostream>

using namespace std;

int S[1000001];
int mcnt[1000];

int main() {
	int n, m;
	long long int in, cnt = 0;

	scanf("%d%d", &n, &m);
	mcnt[0] = 1;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &in);
		S[i] = (S[i - 1] + in) % m;
		cnt += mcnt[S[i]]++;
	}
	cout << cnt;
	return 0;
}