백준 10986번: 나머지 합

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

10986번: 나머지 합

 

이 문제는 누적합 으로 접근해서 풀어야한다.

난 처음에 누적합으로 접근하는 건 알겠는데 (i,j)의 쌍들을 구하는 것을 구현하면 시간제한을 초과할 것 같았다.

즉 다른 방식으로 접근을 해야한다.

그 방법은 d[i]의 배열이 문제에서 주어진 배열의 누적합이라고 하고 A[i]를 문제에서 주어진 배열이라고 할 때

A[i]에서 A[j]의 구간합은 d[j]-d[i-1] 임을 알 수 있다.

문제에서 주어진 답은 (d[j]-d[i])%mod =0 인 구간 (i,j)의 쌍을 구하는 것이다.

즉 d[j]%mod=d[i]%mod 인 구간 i,j를 구하면 된다.

 

백준에서 주어진 예를 들어 보면  

그냥 배열

A	1	2	3	4	5
index	1	2	3	1	2

누적합 배열

d	1	2	3	4	5
index	1	3	6	7	9

누적합 배열 %mod

d%mod(= 3)	1	2	3	4	5
index	1	0	0	1	0

 

즉 나머지 m으로 나누어 떨어지는 구간합 (i,j)은 위의 조건 d[j]%mod=d[i]%mod 에 따라서

1로 같은것 (1,4)  (여기서는 1을 포함안하고 누적합 한다는 의미)

0으로 같은 것(2,3),(2,5),(3,4) 이다

그리고 또 추가해야하는 것이 있는데 (0,2),(0,3),(0,5) 이다 (이유는 0이 곧 첫번째 원소를 포함하고 누적합이다)

 

이제 코드를 보자

#include <iostream>
#include <vector>
using namespace std;
int n,m;
long long cnt[1001];
long long ans,sum;
int main(){
    cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
    cin >>n>>m;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        sum+=a;    //누적합에서 m을 나눈값 
        cnt[sum%m]++;           //개수 늘리기
    }
    for(int i=0;i<=m;i++){
        ans+=(cnt[i]*(cnt[i]-1))/2;
    }
    cout<<ans+cnt[0];

}