[구간 합] 나머지 합 구하기 (백준 10986번) - 파이썬(python)

나머지 합 구하기 (10986번)

시간 제한 : 1초 메모리 제한 : 256 MB

 

---

 

문제

 

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

---

입력

 

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

---

출력

 

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

---

예제 입력

 

5 3
1 2 3 1 2

---

예제 출력

 

7

---

해답

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
numlist = list(map(int, input().split()))
sumlist = [0] * n
remain_list = [0] * m
result = 0

sumlist[0] = numlist[0]

for i in range(1, n):
    sumlist[i] = sumlist[i-1] + numlist[i]
    
for i in range(n):
    remainder = sumlist[i] % m
    
    if remainder == 0:
        result = result + 1
    
    remain_list[remainder] = remain_list[remainder] + 1
    
for i in range(m):
    if remain_list[i] > 1:
        result = result + (remain_list[i]*(remain_list[i]-1) // 2)
        
print(result)

---

풀이

 

나머지 합 문제는 (A+B) % C = ((A%C) + (B%C)) % C 라는 개념을 사용합니다.
위 식을 사용하여 remain_list를 만들고, 구한 remain_list를 조합(Combination) 형식으로 계산해줍니다.