[백준] 나머지 합

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

10986번: 나머지 합

누적합은 맞는데 구간을 구하면서 O(N^2)으로 탐색하다보니 시간이 초과됐다.

그런데 방법을 찾다보니 O(N) 혹은 O(M)이라는 시간복잡도를 가질 수 있다.

For문을 돌면서 나머지가 M이 되는 구간을 찾는 것이 아니라, 아예 나머지가 동일한 수끼리 저장을 해놓는다.

그리고 나머지가 동일한 구간합(0에서부터 A까지, 0에서부터 B까지)끼리 빼면 B-A(B>=A라는 전제)는 반드시 M으로 나누어 떨어진다.

그래서 나머지가 동일한 숫자를 remainder라는 배열에 저장한다.

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

int main() {
    long long n, m, num;
    cin >> n >> m;

    vector<long long> arr(n);
    // 나머지 배열
    // 나머지가 동일한 수끼리 빼면 나머지 0
    vector<long long> remainder(m, 0);
    for(long long i = 0;i < n;i++) {
        cin >> num;
        if(i == 0) {
            arr[i] = num;
        }
        else {
            arr[i] = num + arr[i - 1];
        }
        remainder[arr[i] % m]++;
    }
    long long answer = remainder[0];

    for(long long i = 0;i < m;i++) {
        // 나머지가 같은 수 중에 2개 조합
        if(remainder[i]) {
            answer += (remainder[i] * (remainder[i] - 1)) / 2;
        }
    }
    cout << answer << '\n';
}