백준 10986번 - 나머지 합

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

10986번: 나머지 합

• 필요한 배경지식

누적 합 : prefix sum

 

 

 

• 문제 해결 방법

누적합 알고리즘을 이용하여 1번째부터 n번째까지의 수의 합을 S[n]이라고 나타내면

i번째 수부터 j번째까지 수들의 합 S[i,j]를 S[j] - S[i-1]로 나타낼 수 있습니다. 문제 조건에서 S[i,j] % M이 0인 (i,j)쌍을 구해야 하므로 누적합을 이용하여 식으로 표현하면

 

(S[j] - S[i-1])%M = 0을 만족하는 (i,j) 쌍의 개수 이고,

S[j]%M = S[i-1]%M 을 만족하는 (i,j) 쌍의 개수로 표현할 수 있습니다.

 

M은 최대 1000이므로 S[n]%M 의 결과를 아래의 코드와 같이 저장할 수 있습니다. (rm 배열)

rm[i] = k 이라고 할때, k가 2개 이상이라면 2개를 뽑아 한쌍을 만들 수 있으므로 조합공식을 이용해 총 개수를 구하면 문제를 해결할 수 있습니다.

 

 

 

 

• C++ 전체 코드

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

ll N,M;
ll rm[1000]{};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>M;
    ll t, pre=0;
    for(ll i=1; i<=N; i++){
        cin>>t;
        // next -> S[i]%M, pre -> S[i-1]%M 을 뜻함
        ll next = (pre + t) % M; 
        rm[next]++;
        pre = next;
    }

    rm[0]++; // S[0] = 0이 존재해야 함
    ll ans = 0;
    for(int i=0; i<M; i++){
        if(rm[i] < 2) continue;
        ans += rm[i] * (rm[i]-1) / 2;
    }
    cout<<ans;
}