문제 링크

바로가기

문제 풀이

PY

import sys
input = sys.stdin.readline

answer = 0
m, n = map(int, input().split())
numbers = list(map(int, input().split()))
spatial_sum = [0] * m
modified_sum = [0] * n

spatial_sum[0] = numbers[0]
for i in range(1, len(numbers)):
  spatial_sum[i] = numbers[i] + spatial_sum[i - 1]

for sum in spatial_sum:
  if sum % n == 0: answer += 1
  modified_sum[sum % n] += 1

for sum in modified_sum:
  answer += sum * (sum - 1) // 2

print(answer)

풀이

5 3
1 2 3 1 2

위와 같이 입력을 받는다고 하면 먼저 구간합을 구해보자.

1 3 6 7 9

이렇게 될 것이다. 이러면 일단 순서대로 더했을 때의 나머지를 구할 수 있다. 나머지를 구해보면

1 0 0 1 0 -> arr

이렇게 나온다. 그러면 일단 0인 애들은 나누어 떨어지기 때문에 카운트를 세준다.

그 다음부터는 새롭게 알게 된 사실인데 나머지 값이 같은 애들끼리 두 개를 조합할 수 있는 경우의 수를 구한다.

나머지를 구한 배열을 arr이라고 하면,
arr[0]과 arr[3]은 1로 원소가 같고,
arr[1], arr[2], arr[4]는 0으로 원소가 같다.

arr[0]의 구간합은 1이고 arr[3]의 구간합은 7이다.
7 - 1은 6으로 나누어 떨어진다.

arr[1], arr[2], arr[4]도 같은 방식이다.
arr[2]의 구간합은 6이고 arr[4]의 구간합은 9이다.
9 - 6은 3으로 나누어 떨어진다.

이런 방식으로 나머지가 같은 애들끼리 두 개를 조합하면 갯수를 확인할 수 있다.
(두 개인 이유는 시작점과 끝점으로 두 개인 것)

이렇게 해서 모든 경우의 수를 계산하면 3 + 3 + 1 = 7 이렇게 나온다.

새롭게 배운 점

1. 프로그래머스랑 백준이랑 정답 체크 방식이 달라서 입력 출력하는데 신경 쓸 필요가 있다. 원래는 input() 만을 사용해서 풀었었는데 그럴 경우 너무 느려졌는데 다음과 같은 이유가 있었다.

   input() 은 매개변수로 prompt message를 받음
   입력받은 값의 개행 문자를 삭제시키고 반환함.

   그래서 아래처럼 전처리 과정이 필요하다.

   import sys
   input = sys.stdin.readline
   
   m, n = map(int, input().split())
   numbers = list(map(int, input().split()))

2. 경우의 수를 구하는 공식은

만약에 원소가 세 개 있고 거기서 두 개로 조합을 하면 n = 3, k = 2가 되는 것이다. 그렇게 되면 3 * 2 / 2 = 3이 나온다.

백준 문제는 자바스크립트로 작성하기 너무 귀찮아서 파이썬으로만..