[백준] 10986번 : 나머지 합

---

🔗 문제 링크

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

10986번: 나머지 합

👩‍💻 코드

#include <iostream>
#include <vector>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    int M;
    cin >> N >> M;
    
    vector<long> S(N, 0);
    vector<long> C(M, 0);
    
    cin >> S[0];
    
    long answer = 0;
        
    for (int i=1; i<N; i++){
        int n = 0;
        cin >> n;
        S[i] = S[i-1] + n;
    }
    
    for (int i=0; i<N; i++){
        int remainder = S[i] % M;
        
        if (remainder == 0){
            answer++;
        }
        
        C[remainder]++;
    }
    
    for (int i=0; i<M; i++){
        if(C[i] > 1){
            answer = answer + (C[i] * (C[i] -1) / 2);
        }
    }
    
    cout << answer << "\n";
}

✏️ 풀이

구간 합 배열(S)를 구한 후 M으로 나눈 후 나머지 배열(C)을 만들면 쉬운 문제라고 생각했다.

하지만 나는 나머지가 0인 경우의 수만 생각했다.

S[j] % M의 값과 S[i] % M의 값이 같다면 (S[j] - S[i] ) % M은 0이다.

이 경우의 수를 놓쳤다.

나머지가 0으로 같은 인덱스의 수는 [1,2],[1,4],[2,4]로 3가지 경우가 나오고,

나머지가 1로 같은 인덱스의 수는 [0,3]으로 1가지 경우가 나온다.

인덱스의 수 중 2개의 숫자를 뽑는 경우의 수로 즉, 3C2와 3C2이다.

고등학교 시절에 배운 경우의 수가 어렴풋이 생각나서 수식을 구현하는건 어렵지 않았다.