144. 10986(나머지 합) - 파이썬

import sys
input = sys.stdin.readline

N,M= map(int, input().split())
num = list(map(int, input().split()))
sum = 0
numRemainder = [0] * M

for i in range(N):
  sum += num[i]
  numRemainder[sum % M] += 1

result = numRemainder[0]

for i in numRemainder:
  result += i*(i-1)//2
  
print(result)

문제요약

다양한 구간의 합에서 M으로 나누어 떨어지는 곳을 구하라.

설명

우선 문제에서 출력이 어떻게 나오는지 알아보자.

먼저 백준의 입력 예시로 알아보면,

이 입력으로 각 인덱스별 시작 구간 합을 아래와 같다.

M으로 나눠지는 누적합이 총 7개다.

이런식으로 진행이 되는 것이다.

 

하지만, 큰 수가 들어왔을 때 시간초과없이 i,j구간의 누적합을 위와같이 구하기란 어렵다.

바로 이때 누적합을 사용한다.

다시 보면 누적합 과정에서 M으로 나누어 떨어지는 (나머지가 0) 수는 3,6,9 총 3개이다.

누적합에서 1과 7은 나머지가 1인 수이다.

 

여기서

나머지가 1인 두 구간을 뽑아서 빼준다면? 나머지가 0이 될것이다. (나머지 1인 구간 - 나머지 1인 구간 = 나머지 0인 구간)

즉, 한번의 누적합을 구할 때 나머지를 따로 뽑아서 저장해두고 각 나머지 인덱스에서 2개의 수를 뽑아주면 나머지가 0인 구간을 구할 수 있다.

 

N,M= map(int, input().split())
num = list(map(int, input().split()))
sum = 0
numRemainder = [0] * M

 

누적합의 나머지를 저장할 배열을 선언해주었다.

index가 M인 이유는 M으로 나눈 나머자의 값이 M을 넘을 수 없기 때문이다.

 

for i in range(N):
  sum += num[i]
  numRemainder[sum % M] += 1

누적합을 구하고 바로 나머지 수 인덱스에 값을 증가시킨다.

 

result = numRemainder[0]

첫 결과에 나머지가 0인 값을 집어 넣는 이유는 나머지가 0인 값들은 2개의 수를 뽑지 않아도 0으로 나누어 떨어지는 구간이기 때문이다.

 

위의 입력으로 설명하면,

누적합 3,6,9 구간은 2개를 뽑지 않아도 0으로 나누어 떨어진다.

 

for i in numRemainder:
  result += i*(i-1)//2

이제 나머지가 같은 구간 두개를 뽑는다.

위 식은 조합을 표현한다.