[백준/G3] 10896 나머지 합

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

42240 736 Python 3

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = list(map(int, input().split()))
ans = 0
total = 0
temp = arr[:]

# 나머지가 같은 수 저장

# 나머지가 같은 경우를 서로 빼면 나머지가 상쇄되므로 
# 문제에서 원하는 나누어떨어지는 구간이 만들어짐
check = [0] * M

for i in range(N):
    total += arr[i]
    temp[i] = total % M
    
    check[temp[i]] += 1


# 각 누적합의 나머지가 0인 경우를 더함
ans += check[0]

# 나머지가 같은 수가 2개 이상일때, 그중 2개를 뽑는 경우의 수
for num in check:
    if num >= 2:
        ans += (num * (num - 1)) // 2

print(ans)

각 누적합 나머지의 합의 경우만 생각했지 나머지의 차를 생각하지 못했다...
풀이를 이해하기 위한 포인트는 나머지의 차를 이용하는 것