나머지 합 C++ - 백준 10986

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

구간합 문제.

문제 접근

어떤 구간합이 $M$으로 나누어 떨어질 때를 구해야 한다.

근데 구간합은 $10^{15}$까지 되어 int 형으로는 커버되지 않는다.

long long을 써도 되지만 메모리 사용량을 줄이기 위해

구간합을 구할때 $M$으로 나눈 나머지만을 기록해주었다.

어떤 구간의 나머지 차가 0이면 그 구간은 $M$으로 나누어 떨어진다는

사실에 기반하여 풀었다.

.
.

이 문제를 처음에 접근할 때에는 투포인터 유형인가 했지만,

사실 본질을 놓치고 있었다.

인덱스 $i$번째로 끝나는 구간은 인덱스가 항상 $i$보다 같거나 작은

인덱스들로 구성된다는 사실이다.

$+$

따라서 인덱스 $i$전에 인덱스 $i$에 해당하는 나머지가 몇번 나왔는지,

나머지가 0인지를 확인해주면 되었다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int n,m;
long long ans=0;
int cnt[1001]={0,};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    vector<int> arr(n); cin >> arr[0]; arr[0]%=m;
    if(arr[0]==0) ans++;
    cnt[arr[0]]++;
    for(int i=1;i<n;i++){
        cin >> arr[i]; arr[i]=(arr[i]+arr[i-1])%m;
        if(arr[i]==0) ans++;
        ans+=cnt[arr[i]];
        cnt[arr[i]]++;
    }
    cout << ans;
    return 0;
}

벡터 개선 버전

#include <bits/stdc++.h>
using namespace std;

int n,m;
long long ans=0;
int cnt[1001]={0,};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    int arr[2]; cin >> arr[0]; arr[0]%=m;
    if(arr[0]==0) ans++;
    cnt[arr[0]]++;
    bool ind;
    for(int i=1;i<n;i++){
        ind=i%2;
        cin >> arr[ind]; arr[ind]=(arr[ind]+arr[!ind])%m;
        if(arr[ind]==0) ans++;
        ans+=cnt[arr[ind]];
        cnt[arr[ind]]++;
    }
    cout << ans;
    return 0;
}