- 문제 링크
백준 10986번 - 나머지 합
해결 전략
본 문제는 컴퓨터공학과 학부 과정에서 '이산 수학'을 배운 이라면 반드시 한 번 이상은 들어봤을 '모듈러 연산 관련 공식'을 사용하면 해결할 수 있는 문제이다. 본인은 최초 풀이 시도에서 해당 공식을 떠올리지 못해 해결하지 못했었다.
기본적으로 누적합을 이용하는 문제임은 어렵지 않게 알아차릴 수 있다. 문제는 그 사용 방법이다.
부분 구간의 합을 Area(i+1,j)라 하면, 'Area(i+1,j) = Psum(j) - Psum(i)'임은 자명하다.
부분 구간의 합이 M으로 나뉜다는 것은, (Psum(j) - Psum(i)) % M = 0임을 의미한다.
Modular 연산 공식에 의해, '(Psum(j) - Psum(i)) % M = 0'는
'Psum(j) % M = Psum(i) % M'로 변환할 수 있다.
~> 그렇다. 본 문제는 Index에 대해 누적합을 구하되, 각 누적합의 Modular 연산 결과가 같은 녀석끼리 묶어, 그들로부터 경우의 수를 도출하면 되는 문제이다.
문제의 예시를 토대로 이해해보자.
입력꼴 : 1 2 3 1 2
누적합 : 1 3 6 7 9
모듈라 : 1 0 0 1 0
~> 11/000의 두 묶음으로 분류할 수 있다. 각 묶음에서 단 방향 조합의 경우의 수를 뽑아내는 것은 단순한 연속합 공식을 통해 계산할 수 있다.
이때, 한 가지 더 주의할 점이 있다. M으로 Modular 연산한 결과 나머지가 0에 대해선, 이를 mod[0]이라 하면, 이 mod[0]은 최종 Count값에 더해주어야 한다.
M이 2이상부터이므로, 0묶음에 대해선, 하나 더 있다고 봐야한다. 즉, 위 예시에선 010010, 즉, 11/0000으로 봐야하는 것이다.
~> 엄밀한 예외처리가 요구되는, 상당히 난도가 있는 문제이다. 모듈라 공식은 자주 사용되는 공식이니 늘 기억하도록 하자.
아래는 정답 코드이다.
#include <iostream>
// BOJ - 10986 Remainder Summation
using namespace std;
long long mod[1001];
int main(void) {
int n, m, t;
long long psum = 0, cnt = 0;
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> t;
psum += t;
mod[psum % m]++;
}
for (int i = 0; i <= m; i++)
cnt += ((mod[i] * (mod[i] - 1)) / 2);
cout << mod[0] + cnt;
return 0;
}