[백준] 10986번: 나머지 합(Python)

문제 링크

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

10986번: 나머지 합

 

풀이

풀이 설명

• 분류: 누적합
• 모듈러 합의 개념을 알아야 함.
  •  (A + B) %  M = ((A % M) + (B % M)) % M
  • 덧셈 뿐 아니라 뺄셈, 곱셈 다 해당됨
• 구간의 합은 누적합 배열에서의 차와 같다. ex. i~j 까지의 부분합 = sum[j] - sum[i-1]
• 그러므로, 구간의 합 % M = 0 ->  (sum[j] - sum[i-1]) % M  = 0 -> ((sum[j] % M) - (sum[i-1] % M)) % M = 0 

즉, sum[j] % M = sum[i-1] % M 

• 그러므로 누적합 배열의 항목에서 M으로 나눴을 때 나머지가 같은 쌍을 찾으면 된다. 
• 쌍의 개수를 구한 후 마지막에 나머지가 0인 항목들은 다시한번 따로 세어야 한다.
  • (해당 합까지 온 누적합 자체가 % M = 0 이라는 의미이므로)

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
array = list(map(int, input().split()))

# mod 값이 같은 배열 갯수 -> cnt[1] = 4 -> 나머지 값이 1인 누적합 항이 4개
cnt = [0] * m
ans = 0
prefix = 0

for i in range(n):
    prefix += array[i]
    cnt[prefix % m] += 1

for i in range(m):
    ans += cnt[i] * (cnt[i]-1) // 2

ans += cnt[0]

print(ans)