[Algorithm/C++17] 백준 10986 나머지 합

문제

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

10986번: 나머지 합

풀이 방법

[i, j) 부분 구간의 합이 M으로 나누어 떨어지는 i, j 쌍의 개수를 구하는 문제이다.

배열의 크기 N과 나누는 수 M이 큰 숫자이기 때문에 모든 경우를 계산해보는 방법은 불가능하다. 때문에 배열을 입력 받을 때 부분 합을 미리 계산해놓는다.

 

PrefixSum[j] - PrefixSum[i] % M = 0이 만족하면

PrefixSum[j] % M = PrefixSum[i] % M도 만족한다.

예를 들면 구간 합[A] % M = 1이고 구간 합[B] % M = 1 이면 (A, B)의 구간합 % M은 0이 된다.

즉, 정답 = (구간 합 % M이 0인 개수) + (구간 합 % M이 k인 쌍의 개수)가 된다.

이를 위해서 count 배열에 구간 합 % M = k인 개수를 저장해놓는다.

코드

#include <cstdio>
using namespace std;
int main()
{
    int N, M, sum = 0;
    int count[1001] = {0,};
    scanf("%d %d", &N, &M);
    for(int i=0; i<N; i++)
    {
        int A;
        scanf("%d", &A);
        sum = (sum + A)%M;
        count[sum]++;
    }
    long long answer = 0;
    for(int i=0; i<M; i++)
    {
        answer += (long long)count[i] * (count[i]-1)/2;
    }
    printf("%lld", count[0] + answer);
    return 0;
}

고찰

구간 합으로 특정 부분 구간의 합을 구하는 것만 접해봐서 꽤 어려웠던 문제이다. 모듈로 연산의 특성을 생각해봐야하는 문제.