[C++] 백준 10986번: 나머지 - Prefix Sum

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

---

 

풀면서 그렇게 어려운 문제는 아니었으나, 오랜만에 보니 잘 기억이 안나서 정리

 

연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하라는 문제인데,

보자마자 배열에 나머지만을 저장해도 되겠다는 생각이 들었다.

또한, 연속된 구간의 개수이므로 누적합을 이용해야지 시간초과를 방지하지 않을까라는 생각도 들었다.

#include <iostream>
using namespace std;
int sum[1000001], cnt[1001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    long long ans=0;
    int n, m, t; cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> t;
        sum[i]=sum[i-1]+t%m;
    }
    for(int i=1; i<=n; i++){
        t=sum[i]%m;
        ans+=cnt[t]++;
        if(!t) ans++;
    }
    cout << ans;
}

 

그러므로 우선 sum 배열에는 i부터 현재까지의 합의 나머지를 저장해주었고,

이후에는 sum[i] 원소 값을 m으로 나눈 나머지를 따로 변수로 빼서 저장했다.

이는 이미 나왔던 값이 또 발생한다면, 해당 값을 대체할 수 있는 구간이 존재한다는 것을 의미한다.

즉,

5 3

1 2 3 1 2 라고 주어졌을 때,

0번째 인덱스의 1이 포함된 구간은 4번째 인덱스의 1로 대체가 가능하다.

또한, 해당 변수 t 자체가 0이 되는 경우도 가능하므로 따로 계산을 진행해야한다.