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

백준 10986번 나머지 합 문제 링크

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

10986번: 나머지 합

 

문제 풀이

백준 10986번 나머지 합 문제는 누적합을 이용한 문제로 [i, j] 구간 합이 M 으로 나누어 떨어지는 경우의 수를 세는 문제입니다. 해당 문제를 모든 구간 합을 구해서 M으로 나눌 경우, 시간 초과가 발생하게 됩니다. 그 이유는 N 값이 10^6 이기 때문에 O(N^2) 방법으로는 문제를 해결할 수가 없습니다. 

 

이 문제의 핵심은 구간 합의 나머지가 같은 것들끼리 그룹을 형성한 후, 나머지가 같은 두 개의 구간 합을 서로 빼주게 되면 나머지가 0이 되면서 구간 합이 M으로 나누어 지는 경우를 쉽게 찾을 수 있게 됩니다. 

 

예를 들어, [1 ... j ] 라는 구간이 있을 때, sum(1... j) - sum(1 ... i)  (i <= j) 연산을 하게 되면 sum(i + 1 ... j)의 구간 합이 나오게 됩니다. 이와 같이 두 구간 합의 차이는 특정 구간의 합이 되는 것을 알 수 있습니다. 

 

나아가, 구간 합을 M으로 나눈 나머지 값이 동일한 그룹에서 2개를 선택하여 연속된 구간의 합 ( B - A ) 을 M 으로 나눌 경우 나머지가 0이 됩니다. 

 

즉, 나머지 값이 동일한 구간 합들 중 2개를 선택한 경우를 모두 더하게 되면 구간 합에서 M으로 나누어지는 경우의 수를 구할 수 있게 되는 것 입니다.

 

위 방식으로 문제를 해결하게 될 경우, O(N + M) 만에 문제를 해결할 수 있습니다. 

 

소스 코드

#include <bits/stdc++.h>
#define SIZE 1000010
using namespace std;

typedef unsigned long long ull ;
typedef long long ll; 
ull A[SIZE] ;
ull S ; 
int N, M ;
ll cnt ; 
int main() {
    ios::sync_with_stdio(0); cin.tie(0) ; 

    cin >> N >> M ;
    for (int i = 0, k; i < N ; i++) { 
        cin >> k; 
        S = (S + k % M) % M ; 
        A[S]++;
    }

    A[0]++;

    for (int i = 0; i < M ; i++) {
        if ( A[i] < 2 ) continue ;
        cnt += A[i] * (A[i] - 1) / 2;
    }
    cout << cnt << '\n';
    return 0;
}