[백준 10986번] 나머지 합 (Python/파이썬)

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

10986번: 나머지 합

문제를 딱 보자마자 드는 생각은 모든 경우의 수를  m으로 나누고 나누어 떨어지면 answer += 1 하는 생각이 들었지만 당연히 이렇게 하면 시간초과가 뜰게 뻔하다. 그래서 고등학교 때 수학에서 배웠던 것들을 사용하여 풀었다.

고등학교 때 수열을 하면서 부분합을 배웠었고, 어떤 두 수를 나누었을 때 나머지끼리 빼서 0이 되면 원래 나누기 전의 수끼리의 차도 나누어 떨어진다는 것도 배웠다.

m = 3, [1, 2, 3, 1, 2]가 있다면 합 배열은 s = [1, 3, 6, 7, 9]가 되고, 나머지 배열은 r = [1, 0, 0, 1, 0]이 된다. 

특정 구간의 합이 나누어 떨어져야함으로 구간 i~j까지라고 하면 나머지 배열의 구간에서 r[j] - r[i] = 0 인 구간을 찾으면 된다. (나머지 배열의 차 = 0 이므로 구간합이 나누어 떨어진다는 뜻, 간단히 숫자를 넣어보면 이해하는데 도움이 될 것이다.)

 

→ 구간합을 m으로 나눈 나머지가 나누어 떨어지는 수 = 나머지 배열의 0 개수 + 나머지 배열의 두 수의 차가 0이 되는 개수

(문제에서는 단일 원소가 나누어떨어져도 구간으로 친다)

나머지 배열의 0 개수는 원소를 추가할 때 바로 카운트 했고, 차가 0이 되는 수는 Counter함수를 통해 같은 수의 개수를 구해 조합으로 구하였다.

 

코드는 다음과 같다

import sys
from collections import Counter
input = sys.stdin.readline
n, m = map(int, input().split())
num = list(map(int, input().split()))
sum_list_divided = [0]
answer = 0

## value Combination 2
def com(value):
  if value == 0 or value == 1:
    return 0
  else:
    total = value*(value-1) // 2
    return total

## 합 배열을 m으로 나눈 나머지 배열 생성 & 0 개수 카운트
for i in range(n):
  remainder = (sum_list_divided[-1] + num[i]) % m
  sum_list_divided.append(remainder)
  if remainder == 0:
    answer += 1
sum_list_divided.remove(0)

## 나머지 배열에서 조합 카운트
dic = Counter(sum_list_divided)
for key in dic:
  answer += com(dic[key])
print(answer)

 

추가적인 조언, 질문 모두 환영합니다