[Algorithm] BOJ 10986 : 나머지 합

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    long long N,S; cin >> N >> S;
    long long arr[1000001]= {0};
    long long sum = 0, cnt = 0;

    for ( long long i=0;i<N;i++) {
        int num; cin >> num;
        sum += num;
        arr[sum % S]++;
        if(sum % S==0) cnt++;
    }

    for (int i = 0; i < S; i++) {
        cnt += arr[i] * (arr[i] - 1) / 2;
    }
    cout << cnt << "\n";
}

 

위 문제를 저는 누적합 방식을 이용하여 풀이 했습니다. 결국 가장 이해가 안되는 로직이자 핵심 부분은 아래  두 부분이라 생각됩니다.

arr[sum % S]++;

추후 있을 i...j 까지의 합 중 S로 나누면 0 인수를 찾아 내기 위한 과정입니다.

예를 들어 3, 6, 9 인 경우 모두 3으로 나누면 0이 되기에 그러한 경우를 배열 안에 한번에 담는다고 생각하면 될거 같습니다.   

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

조합의 방법을 이용 했습니다. 예를 들어 10개 중 2 개를 고를 경우 우리는 10*9/2 = 45 과정을 통해 답을 도출 할 수 있습니다.

이러한 아이디어에 근거하여 나머지가 1인 케이스, 2인 케이스 ... 등등 같은 경우의 수 중 2 가지를 뽑아 조합 한다면 나머지가 0 인 답을 차자아 낼 수 있습니다.