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

10986번: 나머지 합

누적 합을 이용한 문제이다. 먼저 배열을 입력받을 때 누적 합들을 구해 S에 저장을 해주었다. 그 후 M과의 나머지 각각의 수를 rem에 카운트를 해준다. 여기서 나머지가 0이 되는 (i, j)를 찾아주면 된다. 만약 (S[j] - S[i]) % M = 0 을 만족한다면 S[j] % M = S[i] % M 또한 만족하게 된다. 나머지 각각의 경우의 수를 구해 result에 더해준 뒤 나머지가 0인 경우인 rem[0] 또한 더해주고 출력을 해주었다. 누적 합을 이용한 문제는 처음이라 굉장히 신박했다. 자주 사용될 유용한 로직이니 잘 기억해두어야 겠다.

#include <iostream>

using namespace std;

int M, N;
long long result = 0;
int A[1000001];
long long S[1000001];
long long rem[1000];

void solution() {
    for (int i = 1; i <= N; i++) {
        rem[S[i] % M]++;
    }

    for (int i = 0; i < M; i++) {
        long long tmp = rem[i] * (rem[i] - 1) / 2;
        result += tmp;
    }

    result += rem[0];

    cout << result;
}

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

    cin >> N >> M;

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

    solution();

    return 0;
}