[백준] 나머지 합

문제

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

10986번: 나머지 합

 

---

풀이

import sys
input = sys.stdin.readline
n,m = map(int, input().split())
a = list(map(int, input().split()))
s = [0] * n # 합 배열
c = [0] * m	# 같은 나머지의 인덱스를 카운트 하는 리스트
answer = 0

s[0] = a[0]
for i in range(1, n):
    s[i] = s[i-1] + a[i]	# 합 배열 저장

for i in range(n):
    rem = s[i] % m	# 합 배열을 m으로 나눈 나머지 값
    if rem == 0:
        answer += 1
    c[rem] += 1

for i in range(m):
    if c[i] > 1:
        answer += (c[i]*(c[i]-1)//2)	# C[i] 개 중 2개를 뽑는 경우의 수 계산

print(answer)

 

---

설명

- 구간 합 배열을 이용해야 함

1. (A+B)%C는 ((A%C) + (B%C)) %C 와 동일하다. => 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다.

2. S[j] % M 의 값과 S[i] %M의 값이 동일하면 (S[j] - S[i]) %M은 0이다.

=> 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트 하고 S[j] 와 S[i] 가 같은 (i, j) 쌍을 찾으면 원본 리스트에서 i+1 부터 j 까지의 구간 합이 M으로 나누어 떨어진다는 것을 알 수 있다.