[백준 10986번] 나머지 합 (C++)

문제링크 : https://www.acmicpc.net/problem/10986

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N, M;
ll arr[1000001], sum[1000001], cnt[1001];

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    for(int i=0; i<N; i++) cin >> arr[i];
    sum[0] = arr[0]%M;
    cnt[sum[0]]++;

    for(int i=1; i<N; i++) 
    {
        sum[i] = (arr[i] + sum[i-1])%M;
        cnt[sum[i]]++;
    }

    ll answer = cnt[0]; //초기값 

    for(int i=0; i<M; i++)
    {
        answer += cnt[i]*(cnt[i]-1)/2;
    }

    cout << answer;
    return 0;
}

 

단순 2중 for문으로 풀면 시간초과가 나는 문제이다.

모듈러 연산을 통해 나머지가 같은 값들을 체크할 필요가 있다.

입력값 1 2 3 1 2
누적합 1 3 6 7 9
나머지 1 0 0 1 0

 

이를 통해 나머지가 같은 경우를 체크해서 저장해준다.

특정 구간 합이 M으로 나누어 떨어지는 경우는 먼저 누적합을 구해주고, 이를 통해 구간을 체크할 수 있다.

i까지의 누적합 : sum[i]
i+1~j까지의 누적합 : sum[j] - sum[i]

체크해야할 것 : (sum[j]-sum[i])%M=0
sum[j]%M - sum[i]%M = 0
sum[j]%M = sum[i]%M

 

위 공식을 통해 만족하는 i, j 쌍의 개수를 구해야하는 것을 알 수 있다.

조합을 통해 나머지가 0으로 같은 경우, 1로 같은 경우, 2로 같은 경우와 같이 같은 케이스 2가지를 골라서 총 경우의 수를 구한다.

 

이는 i=1부터 시작한 누적합에 대해 구해준 것이기 때문에 초기값 i=0부터 시작한 경우도 따로 카운트 해주어야 한다.

ll answer = cnt[0]; 부분 이를 위해 처리해준 값이며, 초기 나머지가 0으로 나누어 떨어진 케이스를 저장해준 것이다.