728x90
https://www.acmicpc.net/problem/10986
10986번: 나머지 합
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j)
www.acmicpc.net
[G3] 나머지 합
문제
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.
즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10**6, 2 ≤ M ≤ 10**3)
둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 10**9)
출력
첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.
예제 입력 1
5 3
1 2 3 1 2
예제 출력 1
7
- 기존의 배열, 누적합(합배열) 모두 각 원소를 M으로 나눈 값으로 전처리
- (a+b)%c = ((a%c) + (b%c))%c 와 같음
- 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일
- (S[i] - S[j-1]) % M = (a[j] + a[j+1] + .... + a[i]) % M = (a[j]%M + a[j+1]%M + .... + a[i]%M) % M = (S[i]%M - S[j-1]%M) %M
- 즉, (S[i] - S[j-1]) % M = (S[i]%M - S[j-1]%M) %M : 부분합 리스트의 각 원소를 M으로 미리 나누고 시작
- S[i]%M의 값과 S[j-1]%M의 값이 같다면 (S[i]-S[j-1]) % M은 0이다.
- 1. 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트
- 2. S[i], S[j-1]가 같은 (i,j)쌍을 찾으면 원본 리스트에서 j ~ i까지의 구간 합이 M으로 나누어 떨어짐
- (i,j)쌍을 찾을 때 완전 탐색 X, dp table을 이용해서 sums 배열의 각 숫자가 나온 횟수 = n -> nC2 이용
- Brute force 방식보다 Dynamic programming 방식이 더 빠름
- DP table의 size는 n+1이 아니라 m+1이다(sums의 최대 원소값이 m이므로)
import sys
input = sys.stdin.readline
# 배열의 크기 : n , 나누는 숫자 : m
n,m = map(int,input().split())
array = list(map(lambda x : int(x)%m, input().split()))
# 합 배열 (누적 합) 구하기
sums = [0] * (n+1)
cnt = 0
for i in range(1,n+1) :
sums[i] = (sums[i-1] + array[i-1])%m
# 구간 합이 m으로 나누어 떨어지는 경우의 수 구하기 (i부터 j까지)
# S[i], S[j-1]가 같은 (i,j)쌍을 찾으면 원본 리스트에서 j ~ i까지의 구간 합이 M으로 나누어 떨어짐
dp = [0] * (m+1)
# 각 숫자가 나온 횟수를 업데이트
for i in sums :
dp[i]+=1
# (i,j)쌍 찾기
for i in dp :
cnt+=(i*(i-1))//2
print(cnt)728x90
