https://www.acmicpc.net/problem/10986
10986번: 나머지 합
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j)
www.acmicpc.net
n, m = map(int, input().split())
nums = list(map(int, input().split()))
remain_count = [0 for _ in range(m)]
remain_count[0] = 1
a = 0
for i in range(1, n+1):
a += nums[i-1]
a %= m
remain_count[a] += 1
answer = 0
for i in range(m):
a = remain_count[i]
answer += (a*(a-1)//2)
print(answer)
숫자 배열 [1, 2, 3, 1, 2] 가 있다고 해보자.
이 배열의 누적합 배열을 구하면 [0, 1, 3, 6, 7, 9]이다.
m이 3일 때 %m 을 해준 값은 [0, 1, 0, 0, 1, 0]이다.
여기서 구간합이 나누어 떨어지려면 %m을 해준 배열에서 같은 값을 가지는 원소 2개를 선택해주면 된다.
예를 들어 [0, 1, 0, 0, 1, 0]에서 두번째 숫자 1과 다섯번째 숫자 1을 선택한다는 것은 누적합에서 1과 7을 선택한다는 것이고, 이는 원래 숫자 배열에서 2, 3, 1의 구간합(=6)을 의미한다.
그래서 remain_count 배열에 나머지값이 등장하는 횟수를 기록한 후, nC2를 이용하여 계산해주었다.
댓글