[백준]10986번 나머지 합 python

 

 

 

이 문제는 수학적인 규칙을 찾는게 어려웠던 문제 이다.

 

규칙을 찾고 나면 코드는 굉장히 간단해서 살짝 허무할 정도다...ㅎ

 

 

 

일단 순서대로 누적합을 구해본다

 

1 2 3 1 2

 

의 누적합은

 

1 3 6 7 9 가 된다

 

이때 문제를 풀기 위해 가장 중요한 규칙은

 

M으로 나눈 나머지가 같은 누적합 A, B가 있을 때 A~B까지의 구간의 누적합은 M으로 나누어 떨어진다.

 

 

 

 

정리하자면 위와 같다

 

 

그래서 이를 토대로 각 나머지의 경우의 수를 구하고

예를 들어, M이 3이라면 나머지가 0인 경우의 수 중 2개를 고르는 조합의 수, 1인 경우의 수 중 2개를 고르는 조합의 수, 2인 경우의 수 중 2개를 고르는 조합의 수를 모두 더해주면 된다.

 

 

정답 코드

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

#각 나머지의 경우의 수 저장하는 배열
r = [0] * m
pre_sum = 0
for i in range(n):
    pre_sum += arr[i]
    r[pre_sum%m] += 1

ans = r[0]

#나머지의 값이 같은 두 부분합 사이의 구간의 부분합은 M으로 나누어 진다
for i in range(m):
    ans += r[i]*(r[i]-1) // 2

print(ans)