[백준] 나머지 합 (10986번) - Python

✅문제 - 나머지 합

---

 

✅필요 알고리즘 개념 - 누적합

---

🔵Prefix Sum (구간 합)

◼ 누적합 문제의 경우 Prefix Sum을 이용해 문제를 푼다. 아래의 예시를 보자

num_list = [1,2,3,4,5]
accum = 0
for i in range(n):
    accum += num_list[i]
    print(accum,end=" ")

위와 같은 코드를 실행시키면 아래와 같은 결과를 얻을 수 있다.

✅코드

---

import sys
input = sys.stdin.readline

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

rem_list = [0 for i in range(m)]
rem_list[0] = 1

accum = 0
for i in range(n):
    accum = (accum + num_list[i])%m
    rem_list[accum] += 1

result = 0
for i in range(m):
    num = rem_list[i]
    if num <= 1:
        continue
    else:
        result += num*(num-1)//2

print(result)

✅코드 설명

---

rem_list는 index는 m으로 나눈 나머지의 개수를 세는 list이다.
accum은 누적합을 저장하는 변수이다.
accum을 구한 후 m으로 나누고 rem_list[accum%m] 의 값을 1 증가 시킨다.

이 때 위의 코드에서 rem_list[0] = 1을 해준 이유는 앞에 아무것도 선택하지 않았을 때의 값 0 을 추가하기 위해서이다.

여기 까지 진행한 결과는 다음과 같다.

구간 합은 prefix_sum[end] - prefix_sum[start-1] 을 통하여 구할 수 있다.
❗❗❗❗ 이 때 ! 구간 합이 m으로 나누어 떨어지기 위해서는 prefix_sum[end]%m의 값과 prefix_sum[start - 1]%m의 값이 같아야 한다! 그러면 뺏을 때 나머지가 0이 되기 때문이다.

그러므로 m으로 나눈 나머지가 0 이 되는 구간 합은 나머지가 같은 두 수를 고르면 된다.
그러므로 rem_list를 순회하며 value Combination 2를 해주면 된다.
그 코드는 아래와 같다.

result = 0
for i in range(m):
    num = rem_list[i]
    if num <= 1:
        continue
    else:
        result += num*(num-1)//2