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

문제

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

 

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10^6, 2 ≤ M ≤ 10^3)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 10^9)

 

출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

 

풀이

#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> res_vec(N, 0);
    long num;
    long res_num=0;
    
    for (long i=0;i<N;i++){
        cin >> num;
        res_num = res_num + num;
        res_num = res_num%M;
        res_vec[res_num]++;
    }
    
    long result=0;
    result = result + res_vec[0];
    
    for (int i=0;i<M;i++){
        if (res_vec[i]>1){
            result = result + res_vec[i]*(res_vec[i]-1)/2;
        }
    }
    
    cout << result << endl;
    
    return 0;
}

 

참고로 위 풀이는 99%에서 틀렸다는 판정이 나온다. 맞는 풀이는 아래와 같다.

 

#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);
    long answer=0;
    cin >> S[0];
    
    for (int i=1;i<N;i++){
        int temp=0;
        cin >> temp;
        S[i] = S[i-1] + temp;
    }
    
    for (int i=0;i<N;i++){
        int remainder = S[i]%M;
        if (remainder==0){
            answer++;
        }
        C[remainder] = C[remainder] + 1;
    }
    
    for (int i=0; i<M;i++){
        if (C[i]>=1){
            answer = answer + C[i]*(C[i]-1)/2;
        }
    }
    
    cout << answer << endl;
    
    return 0;
}

 

틀린 풀이를 올린 이유는 왜 틀렸는지 모르겠어서 올렸다. 혹시 이유를 아시면 말씀해주시면 감사하겠습니다.