[파이썬] 백준 10986 : 나머지 합 (골드3)

[파이썬] 백준 10986 : 나머지 합 (골드3)

• https://www.acmicpc.net/problem/10986
  

---

풀이

방향성 생각

• 이제까지 등장한 누적합%M과 같을 경우, 매칭이 가능하다.
• 순회를 한 번 하면서 누적합에 기록된 숫자들을 딕셔너리에 기록한다.
• 누적합에 기록된 숫자 자체가 M으로 나누어 떨어지면, 혼자 만으로 정답 체크가 된다.
• M으로 나누어 떨어지는 경우에는 KC2 + K, 아닌 경우에는 KC2를 카운팅한다.

---

전체코드

# %%
from collections import defaultdict as dd

N,M = map(int,input().split())
arr = list(map(int,input().split()))

S = [arr[0]%M]
for v in arr[1:]:
    S.append((S[-1]+v%M)%M)

table = dd(int)
for s in S:
    table[s] += 1

answer = 0
for i in table.keys():
    v = table[i]
    if i==0:
        answer += v*(v+1)/2
    else:
        if v>1:
            answer += v*(v-1)/2
print(int(answer))

코멘트

• 규칙만 찾으면 쉬운 문제
• 처음 예시를 보면 S = [1,0,0,1,0]이 나오는데 1 1로 구간 잡는 경우를 빼먹어서 생각하는데 조금 걸렸다.