10986번 - 나머지 합 구하기 5(C++)

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

 

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

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

 

이게 무슨 말인가 보자

 

i번째부터 j번째까지의 구간합을 M으로 나누었을때 값이 0이 되는 경우의 수를 구하는 문제다.

 

일단 저번에 풀었던 1차원배열 구간합공식으로 구간합배열을 구하고 그 배열을 다시 M으로 나눠서 값을 바꾼다.

 

그렇게 했을때 배열[i]의 값이 0이라면 0번째부터 i번째의 구간합 나머지가 0이라는 뜻. => 구간합 나머지 배열에서 0의 갯수를 경우의수(answer)에 추가

 

다음으론 S[i]~S[j]의 경우의 수를 구해야 하는데 어떻게 해야할까

S[i]~S[j]의 구간합은 S[j]값에서 S[i]값을 빼서 구한다. 그렇다면 나머지도 똑같다. 새로 만들어진 구간합 나머지 배열에서

S[i]-S[j] = 0이 되는 그러니까 같은 나머지값을 가지는 인덱스 2개의 조합을 찾으면 된다.

 

예를 들어 나머지가 1인 인덱스가 3개라면 $${\mathrm{3C2}}^{}$$= 3으로 모든 경우의 수 answer에 추가 이런식으로 해결했다.

 

다음은 코드다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // C++의 iostream과 C의 stdio 동기화 비활성화 (입출력 속도 향상)
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    long answer = 0;

    cin >> N >> M;

    // 누적합 배열 (0부터 i번째 원소까지의 합)
    vector<long> S(N, 0);
    // 나머지 배열 (S[j] % M이 같은 누적합의 개수를 세기 위한 배열)
    vector<long> C(M, 0);

    cin >> S[0];
    for (int i = 1; i < N; i++) {
        int temp;
        cin >> temp;
        S[i] = S[i - 1] + temp;
    }

    // 나머지가 0인 경우 바로 정답에 추가
    for (int j = 0; j < N; j++) {
        int remainder = S[j] % M;
        if (remainder == 0) {
            answer++;
        }
        // 나머지가 remainder인 누적합 개수 세기
        C[remainder]++;
    }

    // 나머지가 같은 누적합 2개를 선택하는 경우의 수를 더함 (nC2)
    for (int k = 0; k < M; k++) {
        if (C[k] > 1) {
            answer += (C[k] * (C[k] - 1)) / 2;
        }
    }

    cout << answer << "\n";
    return 0;
}