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

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

10986번: 나머지 합

나머지 합 문제

N개의 수의 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 문제

정말 딱 한 부분을 생각 못해서 내 자력으로는 풀지 못한 문제였다. 힌트를 참고하여 해결!

정답 코드

import sys
N, M = map(int, sys.stdin.readline().split())
x = list(map(int, sys.stdin.readline().split()))+[0]
r = [0]*M
for i in range(N):
    x[i] += x[i-1] # 누적합 
    r[x[i] % M] += 1 # 누적합을 M으로 나눈 나머지를 인덱스로 해당 인덱스에 해당하는 r값 1씩 증가
cnt = r[0]

for i in r:
    cnt += i*(i-1)//2 # r의 값에서 2개를 조합하여 뽑을 때 값

print(cnt)

먼저 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수이므로 구간 합을 구해줄 필요가 있다.

구간합을 구해주고 나서, 이때의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 하므로, M으로 나누었을 때를 인덱스로 해서 r에 넣어주면 각 나머지의 갯수를 알 수 있다.

여기까지는 스스로 생각해 냈는데, 이때 합이 M으로 나누어 떨어지는 (i,j) 쌍의 갯수를 구하는 부분을 직접 생각해내지 못했다. r의 0 인덱스에 해당하는 값은 이미 M으로 나누어 떨어지므로 초기값 cnt는 r[0]이다.

여기서, 누적합의 나머지가 같은 것들 중에서 2개를 조합하게 되면 M으로 구간이 나누어 떨어지게 된다.

이 말은 예를 들어 나머지가 1인 것 중에 2개를 뽑을 경우, 2개의 나머지의 차이인 1-1 = 0이 되어서 연속된 부분 구간의 합이 나누어 떨어지게 된다는 것이다.

예제 입력을 예로, 3으로 나누어 떨어지는 구간 합의 나머지가 1인 경우는 (1, 1+2+3+1 = 7)의 2가지가 있다. 여기서 뒤에 요소들과 앞의 요소들에 해당하는 부분만큼 제외한 2+3+1을 선택하게 되면 나머지가 0이 되는 식으로 구성을 하면 나누어 떨어지는 구간 합을 알 수 있다.

---

느낀 점

누적 합을 이용하는 문제들을 풀 때, 꽤나 애를 먹고 있다. 특히나 누적 합은 조금만 반복횟수가 늘어나거나 하는 순간 바로 시간초과가 뜨기 때문에 이를 활용하여 어떻게 풀어낼지를 생각해내야한다.

그런 부분에서 아직 아이디어가 많이 부족하다는 것을 느꼈다. 여러 문제를 풀어보기도하고, 직접 손으로 써내려가면서 아이디어를 떠올려보는 연습을 할 필요성을 느꼈고, 조금 더 유동적으로 생각하는 방법을 길러야겠다고 느꼇다.