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

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

10986번: 나머지 합

---

 

주어진 배열의 구간 합이 m으로 나누어떨어지는 경우의 수를 구하는 문제

제출하고 다른 사람들의 풀이를 보니 다들 조합으로 풀어서 신기했던 문제이다.

조합으로 푸는 방법은 생각지도 못했는데,

다른 사람들의 풀이를 보니 조합으로 접근했어도 괜찮았을 듯 싶다.

 

우선 배열 i ~ j의 누적 합을 구해주는데, 어차피 나머지가 중요하므로 나머지의 누적 합을 구해준다.

이후 현재까지 나온 나머지의 개수를 저장해주고,

현재 값에서 해당 나머지를 뺀 값은 반드시 m으로 나누어떨어지므로

나머지의 개수만큼의 배열이 존재한다는 것을 의미한다.

여기서 나머지가 0인 경우는 자신도 m으로 나누어떨어지므로 1을 더해주면 된다.

 

#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;
}

 

나는 여기서 한 번에 나머지의 개수를 파악하여 더해주었는데,

조합으로 접근한 방법은 나머지의 개수를 파악하여

nC2 조합으로 접근하는 것이었다.