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

문제 링크: https://www.acmicpc.net/problem/10986

10986번: 나머지 합

1. 주의할 점

- 연속된 부분의 누적 합에 대해 알고 있어야 한다

- O(N^2)보다 작은 알고리즘을 구현해야 한다

- 답이 int 범위를 벗어날 수 있다

 

2. 구현

- 나머지가 M으로 나눠떨어지는 누적합은 2가지의 방식이 존재한다(파란 글씨 + 빨간 글씨)

- 값을 입력받으며, Sum[] 함수에 연속된 누적합을 M으로 나눈 값을 저장한다

- 만약 Sum[i]의 값 즉 0~i 인덱스까지의 합이 M으로 나누어 떨어지면 Result++를 수행한다

- Cnt[] 배열에 Sum[] 값이 몇 개 있는지 저장한다

- For문을 0~M까지 돌려서 Cnt[] 배열에 2 이상의 수가 저장된 경우, 2개를 고르는 조합 공식을 사용하여 Result에 더한다. 서로 다른 구간에서 M으로 나눴을 때 나머지가 같으므로 nC2만큼 더한다

 

#include <iostream>
using namespace std;
long long sum[1000000];
long long cnt[1001];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int num, m, val;
	long long result = 0;
	cin >> num >> m;
	for (int i = 0; i < num; i++) {
		int val;
		cin >> val;
		val %= m;
		if (i == 0)	sum[i] = val;
		else sum[i] = (sum[i - 1] + val) % m;
		if (sum[i] == 0) result++;
		cnt[sum[i]]++;
	}
	for (int i = 0; i <= m; i++) 
		result += (cnt[i] * (cnt[i] - 1)) / 2;
	cout << result;
	return 0;
}