[BOJ/C++] 10986(나머지 합)

1. Link

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

• 진짜 어이없게 끝난 문제입니다. 누적 합은 알겠는데 어떻게 풀어야하지 엄청 고민했는데, 한 번 생각나고 나서는 이걸 왜 고민했지 싶었던 문제였습니다.

• 누적 합 뿐 아니라 결과값에 왜 다음과 같이 더해지는지(조합) 알아야 하는 문제입니다. 만약 생소하다면 이런 유형은 익혀두는 것이 좋습니다.(저에게도..)

2. 풀이 과정

1. 연속된 부분 구간의 합(N<=10^6) -> 누적 합
2. ~의 합이 m으로 나누어 떨어지는 구간의 개수 -> 조합(nCr)

• 누적 합은 저런 구절만으로 대략 눈치챌 수 있을 거라고 생각합니다. 사실 세그먼트 트리도 있고, DP도 있고 다양하지만, N 값을 보고 배열이 너무 커질 것이라고 생각했습니다. 따라서 누적 합으로 문제를 풀이했습니다.

• 예제를 들어 문제를 설명해보도록 하겠습니다.
  

풀이 순서
1. 누적 합을 구해야 합니다.
2. 누적 합을 구할 때 나머지 연산으로 값을 단순화합니다.
3. 어떤 구간이 나누어떨어지는 구간인지 파악합니다.
4. 조합을 사용하여 nC2의 꼴로 정답을 구합니다.

1. 이 예제를 보면 누적 합은 1, 3, 6, 7, 9가 됩니다. 이 때 누적합은 최대 (10^6)*(10^9)인데, 굳이 long long 자료형을 쓰지 않고 m으로 나눈 나머지를 입력하면 int만으로 충분하게 해결할 수 있습니다.

2. 따라서 위의 누적 합을 3으로 나눈 나머지를 받는 즉시 대입하면 1, 0, 0, 1, 0이 되며, 나머지 기준 1이 2개, 0이 3개임을 확인할 수 있습니다.

3. 여기서 중요한 점은 나머지끼리 같다면 그 구간은 나누어떨어진다는 것입니다.
   가령 1번부터 4번(1, 1) 배열을 확인해보겠습니다. arr[1] = 1, arr[4] = 1(7%3)이며 그 둘을 빼면 0이 되고, 이는 2번부터 4번의 합이 m으로 나누어떨어짐을 보여줍니다.
   결국 같은 수끼리 더해주면 된다는 뜻이니, 입력 및 값을 m으로 나누는 과정 직후 나머지가 나오는 대로 갯수를 세어주도록 합니다.

4. 다음에 고등학생 때 배운 nCr을 생각하면, nCr은 n개 중에 r개를 순서 상관없이 뽑는 경우의 수였음을 기억할 것입니다. 위에서 설명했듯이 같은 나머지값을 조합하면 결국 0값이 나오고 m으로 나누어떨어지는 것이니, 0부터 m - 1까지 나머지값에 따라 n개 중에 2개를 선택하는 것을 각 경우의 수로 생각하고 정답에 더해주면 결과를 얻을 수 있습니다.

3. 정답 코드

#include<iostream>
using namespace std;
#define ll long long

int n, m, cnt = 0;
ll prefix[1000];

void input() {
	cin >> n >> m;
	int num;
	for (int i = 1; i <= n; ++i) {
		cin >> num;
		cnt = (cnt + num) % m;
		++prefix[cnt];
	}
}

void solution() {
	input();
	ll answer = 0;
	for (int i = 0; i < m; ++i) {
		//nC2, n개중에 2개를 순서 상관없이 선택
		answer += (prefix[i] * (prefix[i] - 1)) >> 1;
	}
	cout << answer + prefix[0];
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
	solution();
	return 0;
}