[백준] 10986번 나머지 합(python)(누적합)

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

10986번: 나머지 합

 

1. 난이도 골드3 (🥇)

 

 

2. 문제 해결 방법

1. 누적 합 개념을 이용해야한다.

 

2. 누적합 % M == 0 인 경우 카운팅해준다.

 

3. (누적 합1 % M) 값과 (누적 합2 % M) 의 값이 같다는 것은 (누적합1 - 누적합2) % M이 0이라는 뜻과 같다.

 

예를 들어

10 % 3 => 1

13 % 3 =>1

(13 - 10) % 3 => 0

즉, 두 누적합을 빼준다는 것은 나머지끼리도 차가 발생해 0이 되는 것

 

따라서 '나머지 값이 같은 인덱스'중  '2개의 원소를 뽑을 수 있는 수'를 조합으로 계산하여 카운팅해주면 된다.

 

나도 잘 이해가 안되어서 구글링했다. 이걸 한 방에 생각하시는 분들은 증말 존경스러워

 

3. 내가 작성한 코드

from math import comb
from collections import Counter

n,m = map(int, input().split())
a = list(map(int, input().split())) #수열
d = [0] #누적합

temp = 0
result=0 

for i in a: #누적합 리스트 생성
  temp += i
  if temp%m == 0:
    result +=1 # 나머지가 0인 경우 카운팅
  d.append(temp%m)

cnt = Counter(d[1:])
cnt = list(cnt.values()) #나머지의 개수 남은 것만큼 카운팅

for i in cnt:
  result += comb(i,2) #나머지의 원소 값이 같은 2개의 원소를 뽑는 경우의 수 카운팅

print(result)

 

4. 수정 코드

import sys

input = sys.stdin.readline

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

a = list(map(int, input().rstrip().split())) + [0]

c = [0] * m

for i in range(n):
  a[i] = a[i-1] + a[i]
  c[a[i]%m] += 1

ans = c[0]

for i in c:
  ans += i * (i-1) // 2

print(ans)