[백준] 10986번 나머지 합 (파이썬)

문제링크: https://www.acmicpc.net/problem/10986

문제해결 아이디어

• 1차원 배열의 누적합 문제이다
• 누적합의 나머지가 같은 수 끼리 빼면 나머지가 0이 된다
• 예제의 누적합의 경우 [1, 3, 6, 7, 9] 인데 나머지가 1인 1과 7을 빼도 나머지가 0이 된다.
• 나머지값 별로 개수를 배열에 저장하고 조합을 통해서 정답을 구한다.

소스코드

import sys

input = sys.stdin.readline

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

nums =  list(map(int, input().split()))

prefix_sum = [0] * n

prefix_sum[0] = nums[0]

for i in range(1,n):
    prefix_sum[i] = prefix_sum[i-1] + nums[i]

mod = [0] * m # 나머지 배열

for i in prefix_sum:
    mod[i%m] += 1 # 나머지가 같은 수의 개수를 구함

answer = mod[0] 

for i in mod:
    answer += i*(i-1) // 2 #조합을 통해 개수를 추가 ex)iC2

print(answer)