[BOJ-10986][C++] 나머지 합

문제

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

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

 

입력

첫째 줄에 N과 M이 주어진다. ($1 ≤ N ≤ 10^6, 2 ≤ M ≤ 10^3$)

둘째 줄에 N개의 수 $A_1, A_2, ..., A_N$ 이 주어진다. ($0 ≤ A_i ≤ 10^9$)

 

출력

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

 

예제 입력 1

5 3
1 2 3 1 2

 

예제 출력 1 

7

 

알고리즘 분류

• 수학
• 누적 합

 

문제 출처

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

10986번: 나머지 합

 

---

 

문제 해결 방법

• 구간 합 알고리즘을 이용하여 풀 수 있는 문제였다.

 

구간 합을 구하는 공식을 문제 해결에 활용하기

• 이 문제는 구간 $[i, \; j]$ 의 구간 합을 M으로 나눈 나머지가 0인 구간의 개수를 출력하도록 만드는 문제이다.
• 구간 $[i, \; j]$ 의 구간 합은 pSum[j] - pSum[i - 1] 으로 구할 수 있고, 나머지 연산은 모듈러(%) 연산자를 이용하여 구할 수 있다. 따라서 다음과 같은 수학식을 작성할 수 있다.

$$(\text{pSum}[j] - \text{pSum}[i - 1]) \text{% M == 0}$$

• 모듈러(%) 연산자는 분배 법칙이 성립하므로, 다음과 같이 식을 전개시킬 수 있다.

$$(\text{pSum}[j] \text{% M}) - (\text{pSum}[i - 1] \text{% M}) \text{== 0}$$

• 따라서 다음과 같은 식이 성립하게 된다.
  • pSum[j] : 첫 번째 인덱스부터 j번째까지의 구간 합(부분 합)
  • pSum[i - 1] : 첫 번째 인덱스부터 i - 1번째까지의 구간 합(부분 합)

$$\text{pSum}[j] \text{% M} \; \text{==} \; \text{pSum}[i - 1] \text{% M}$$

• 이 식의 의미는 첫 번째 인덱스부터 j번째까지의 구간 합을 M으로 나눈 후의 나머지 값과 첫 번째 인덱스부터 i - 1번째까지의 구간 합을 M으로 나눈 후의 나머지 값이 같음을 의미한다.
  • 나머지 값으로는 {0, 1, ..., M - 1}이 될 수 있다.

 

예제를 이용하여 문제 풀기

• 문제에서 주어진 예제 입력 1을 이용하여 문제를 이해해보자. (N : 5, M : 3)

i	0	1	2	3	4	5
num	-	1	2	3	1	2
pSum[i]	-	1	3	6	7	9
pSum[i] % M	-	1	0	0	1	0

•  pSum[i]  % M의 결과값을 크기가 1,001인 cnt배열에 저장해줄 것이다.
  • 문제에서 M의 입력 범위로 $2 ≤ M ≤ 10^3$가 주어졌으므로, cnt 배열의 크기는 넉넉하게 1,001로 지정해준다.

			
			
			
		
for (int i = 1; i <= n; i++) {
    cin >> num;
 
    pSum[i] = pSum[i - 1] + num;    // 구간 합 구하기
    cnt[pSum[i] % M]++;
}

 

• cnt배열에는 구간합 pSum[i]을 M으로 나눈 나머지 값들이 들어 있으며, 다음과 같이 값들이 정리될 것이다.

i	0	1	2
cnt[i]	3	2	0
경우	{1, 2}, {1, 2, 3}, {1, 2, 3, 1, 2}	{1}, {1, 2, 3, 1}	{ }

 

① $\text{pSum}[j] \text{% M} \; \text{==} \; \text{pSum}[i - 1] \text{% M}$ 

• 이제 $\text{pSum}[j] \text{% M} \text{==} \text{pSum}[i - 1] \text{% M}$을 만족시키는 경우의 수를 찾아야 한다.
• 나머지가 0인 경우의 수(cnt[0])에서 2가지 방법을 뽑는 경우($_{cnt[0]}C_{2}$)와 나머지가 1인 경우의 수(cnt[1])에서 2가지 방법을 뽑는 경우($_{cnt[1]}C_{2}$), 그리고 나머지가 2인 경우의 수(cnt[2])에서 2가지 방법을 뽑는 경우($_{cnt[3]}C_{2}$)를 모두 더 해준다.

$$_{cnt[1]}C_{2} + {}_{cnt[2]}C_{2} + {}_{cnt[3]}C_{2} = {}_{3}C_{2} + {}_{2}C_{2} + {}_{0}C_{2} = \frac{3 \times 2}{2 \times 1} + \frac{2 \times 1}{2 \times 1} + 0 = 3 + 1 = 4$$

			
			
			
		
ull Combination(ull n) {
    return (n * (n - 1)) / 2;
}
 
ull Solution(int n, int m) {
    // ...
 
    for (int i = 0; i < m; i++) {
        answer += Combination(cnt[i]);    // nC2 구하기
    }
}

 

참고

• $_{cnt[1]}C_{2}$ : [{1, 2}, {1, 2, 3}], [{1, 2, 3}, {1, 2, 3, 1, 2}] [{1, 2}, {1, 2, 3, 1, 2}]
• $_{cnt[2]}C_{2}$ : [{1}, {1, 2, 3, 1}]
• $_{cnt[3]}C_{2}$: [{ }]
• 각각의 경우의 구간 합을 M으로 나눈 후의 나머지 값이 서로 비슷하므로 $\text{pSum}[j] \text{% M} \; \text{==} \; \text{pSum}[i - 1] \text{% M}$을 만족시킨다.
• 조합(Combination) 공식은 $\displaystyle _{n}C_{r} = \frac{n!}{r!(n - r)!}$ 이며, 이는 $n$개 중에서 순서를 고려하지 않고 $r$ 개를 뽑는 경우의 수를 의미한다. 
  • $\displaystyle _{n}C_{2} = \frac{n!}{2!(n - 2)!} = \frac{n(n - 1)}{2!}$ 이다.

 

② $\text{pSum}[a] \text{% M = 0}$

• 추가적으로 pSum[a] % M = 0인 경우는 단독으로 M으로 나누어 떨어지는 경우이다. ([{1, 2}], [{1, 2, 3}], [{1, 2, 3, 1, 2}]) 
• 따라서 결과 값(answer : 4)에 추가적으로 단독으로 M으로 나누어 떨어지는 경우인 3(cnt[0])을 더해줘야 한다.

			
			
			
		
ull Solution(int n, int m) {
    for (int i = 1; i <= n; i++) {
        cin >> num;
        
        pSum[i] = pSum[i - 1] + num;    // 구간 합 구하기
        cnt[pSum[i] % M]++;
    }
 
    for (int i = 0; i < m; i++) {
        answer += Combination(cnt[i]);    // nC2 구하기
    }
 
    return cnt[0] + answer;
}

 

코드

			
			
			
		
#include <iostream>
using namespace std;
 
using ull = unsigned long long;
 
int N, M, num;
ull pSum[1000001];
ull cnt[1001];
ull answer;
 
void Input() {
    cin >> N >> M;
}
 
ull Combination(ull n) {
    return (n * (n - 1)) / 2;
}
 
ull Solution(int n, int m) {
    for (int i = 1; i <= n; i++) {
        cin >> num;
        
        pSum[i] = pSum[i - 1] + num;    // 구간 합 구하기
        cnt[pSum[i] % M]++;
    }
 
    for (int i = 0; i < m; i++) {
        answer += Combination(cnt[i]);    // nC2 구하기
    }
 
    return cnt[0] + answer;
}
 
void Output() {
    cout << Solution(N, M) << '\n';
}
 
void Solve() {
    Input();
    Output();
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    Solve();
 
    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [누적 합]
• 골드III

 

조합(Combination)

• $n$개 중에서 순서를 고려하지 않고 $r$ 개를 뽑는 경우의 수

$$_{n}C_{r} = \frac{n!}{r!(n - r)!}$$