[C/C++] 백준 - 10986번 : 나머지 합

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

10986번: 나머지 합

문제

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

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

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

출력

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

---

문제도 짧고 이해하기도 쉬운 문제인데 어떻게 구현해야할까?

가장 먼저 접근해야 할 것이 나머지 연산(=모듈려 연산)을 적용해야한다.

가장 먼저 어떻게 적용해야할까 생각해야한다. 이 문제에서 요구하는 건 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수이다.

 

Step 1.

일단 연속된 구간의 합이라는 말이 나왔으니 누적 합을 이용해 좀 더 효율적으로 계산해야한다. 

 

Step 2.

그리고 누적 합을 저장하는 배열의 값들을 M으로 모듈러 연산을 했을 경우 0인 값들은 모두 M으로 나누었을 때 나누어 떨어지는 값들이다. 이건 자명한 사실이다.

 

Step 3.

처음부터 현 구간까지가 아닌 중간 구간 계산값이 M으로 나누어떨어지는 경우의 수도 골라야한다.

즉, (pSum[j] - pSum[i]) % Mod = 0인 구간을 구해야한다. 이 식을 보면 모듈러 연산 식 변환을 통해

pSum[j] % Mod = pSum[i] % Mod로 변환할 수 있다.

 

 

 

문제의 주어진 예시로 어떻게 위 과정들을 적용시키는지 확인해보자.

index	0	1	2	3	4
value	1	2	3	1	2

 

우선 위 처럼 주어진 값들을 누적 합 배열에 저장해보자.

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

 

그리고 다시 위 표에 모듈러 연산을 적용시켜보자.

index	0	1	2	3	4	5
pSum % Mod	0	1	0	0	1	2

 

자, 이제 위 표에서 우리는 구간을 선택해주어야한다.

Step 2.에서 말한 것처럼 인덱스가 0이 아닌 곳에서 pSum % Mod가 0이라면 처음부터 누적해서 더한 값을 모듈러 연산을 했을 경우 M의 배수라는 것이므로 0의 개수부터 세어준다. 

-> 인덱스 2와 3 : 2개

 

그리고, Step 3. 에서 알아낸 pSum[j] % Mod = pSum[i] % Mod인 구간 또한 모듈러 연산을 했을 경우 나머지가 0이 되는 구간이다.

1의 값을 가진 인덱스가 1, 4 -> 즉 2개 존재. {1, 4}

2의 값을 가진 인덱스가 5 -> 존재x

 

만약 1의 값을 가진 인덱스가 4개라면?

ex) {1, 4, 5, 7} 인덱스의 값이 1일 경우 구간은 총 {1, 4}, {1, 5}, {1, 7}, {4, 5}, {4, 7}, {5, 7} : 6개가 된다. -> nC2의 결과값과 동일하다는 것을 알 수 있다.

 

---

이제 어떻게 해야할 지 알았으니 구현을 어떻게 해야할 지 생각하면 된다. 

문제에 주어진 제한 조건을 봤을 때 M의 최대 값은 10^3이다. 매우 큰 값이 아니기 때문에 1000크기의 배열을 만들어 그 안에 각 개수를 저장해주면 된다. 그리고 조합 계산 한 결과를 모두 더해주면 된다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'

using namespace std;

int N, M;
vector<int> num;
long long modNum[1000 + 1];
long long pSum[1000000 + 1];

void input(){
    cin >> N >> M;
    num.resize(N);
    for(int i=0;i<N;i++){
        cin >> num[i];
    }
}

void init(){
    for(int i=1;i<=N;i++){
        pSum[i] = (pSum[i-1] + num[i-1]) % M;
        modNum[pSum[i]]++;
    }
}

long long combination(long long num){
    return ((num * (num-1)) / 2);
}

long long solution(){
	// 초기 값을 modNum[0]으로 하는 이유는 Step 2.에 나와있다.
    long long count = modNum[0];
    for(int i=0;i<M;i++){
    	// Step 3. 과정
        count += combination(modNum[i]);
    }
    return count;
}

int main(){
    fastio;
    input();
    init();
    cout << solution() << endl;

    return 0;
}