10986번: 나머지 합
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j)
www.acmicpc.net
[난이도] Gold4
[유형] 누적합
[풀이]
(i,j) 구간합이 M으로 나누어 떨어지는 경우는
sum(1,j)%M == sum(1,i-1)%M 인 경우이다.
a[1]+a[2]...a[i-1]+a[i]+a[i+1]....a[j]
왜냐하면 j까지의 합이 위와 같고
만약 sum(1,i-1)%M가 k 일때, sum(1,j)%M도 k이려면
sum(i,j)%M은 0이어야 한다.
결국 정답은 나머지가 똑같은 누적합 중에서 두개를 뽑는 경우의 수이다.
#include
int N,M,cnt[1001],sum[1000001];
long long ans;
int main(){
scanf("%d%d",&N,&M);
cnt[0]++;
for(int i=1;i<=N;i++) {
int v;
scanf("%d",&v);
sum[i] = (sum[i-1]+v)%M;
cnt[sum[i]]++;
}
for(int i=0;i<m;i++){ class="hljs-keyword" <span="">int n = cnt[i];
if(n>1) ans+= ((long long)n*(n-1))/2;
}
printf("%lld",ans);
}</m;i++){>
https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/10986.cpp
'Problem-Solving > BOJ' 카테고리의 다른 글
[BOJ/백준][Gold4] 13325 : 이진 트리 (C++) (0) | 2020.12.24 |
---|---|
[BOJ/백준][Gold4] 16929 : Two dots (C++) (0) | 2020.12.24 |
[BOJ/백준][Gold4] 2643 : 색종이 올려 놓기 (C++) (0) | 2020.12.20 |
[BOJ/백준][Gold4] 2457 : 공주님의 정원 (C++) (0) | 2020.12.20 |
[BOJ/백준][Gold4] 1695 : 팰린드롬 만들기 (C++) (0) | 2020.12.20 |