[누적합, 부분합] 백준 10986번 : 나머지 합 / 골드 3

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

10986번: 나머지 합

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를 이용하여 계산해주었다.