[BOJ] 10986번: 나머지 합

https://www.acmicpc.net/

 

문제풀이

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

10986번: 나머지 합

처음에는 누적합을 구하고 그 안에서 만들수 있는 조합에 대한 범위로 모든 경우를 살펴서 나머지가 0인 것을 찾았지만 이는 시간초과가 났다. 아무래도 2중 반복문을 써서 계속 배열에 접근하는게 문제였던 것 같다.

해결할 방식의 경우 다른사람의 풀이를 참고했는데 이해하기가 쉽지 않았다. 따라서 설명을 자세하게 적어보려고 한다.

 

주어진 입력이 다음과 같을 때 우선 누적합의 배열을 구한다.

5 3
1 2 3 1 2

 

누적합의 배열은 다음과 같아진다.

index	0	1	2	3	4	5
value	0	1	3	6	7	9

• 누적합을 구할 때 이전 값을 이용하기 위해서 0번째 인덱스는 0으로 채워 시작했다. 여기서 우리가 i, j 구간에 대한 합을 구하려고 한다면 다음과 같이 구할 수 있다.
• (i, j) = array[j] - array[i-1]
• j까지의 배열의 합에서 i-1번째의 합을 빼게되면 내가 구하고자 하는 범위의 값을 구할 수 있다.

 

이제 각 누적합에 대해서 나머지를 구해본다.

index	0	1	2	3	4	5
value	0	1	0	0	1	0

나머지가 다음과 같이 될 때 생각할 수 있는 점은 나머지가 같은 수를 고르면 주어진 m값 3으로 나누어지는 구간을 찾을 수 있다. 

(2, 4) = array[4] - array[1] = 7 - 1 = 6 

위와 같이 2번에서 4번 구간의 경우 1번에 의해 1이 제거되면서 6이라는 값을 얻게되어 3으로 나누어진다.

여기서 나머지를 살펴보면 나머지가 1로 같은 구간 1과 4를 선택했을 때 실질적으로 2와 4구간이 3으로 나누어지는 구간으로 선택된 것이다. 나머지가 같은경우 이를 위에서의 식처럼 뺄 수 있다고 생각하면 해당 구간이 조건에 충족된다.

 

이는 나머지가 1인 경우만이 아니라 어떤 나머지에서든 같은 두 수를 고르는 조합의 개념이다.

계속하던 예제에 대해서 나머지 배열을 만든다.

index(== 나머지)	0	1	2
value(== 나머지 개수)	3	2	0

 나머지가 1일때를 먼저보면 나머지가 1인 경우는 2개가 존재하고 이 2개중에 2를 뽑는 2C2의 경우로 1가지가 존재한다.

나머지가 0인 경우는 3개가 존재하고 3개중에 2개를 뽑는 3C2의 경우로 3가지가 존재한다.

이때 나머지가 0인 경우 다른 수와 조합하지 않고 본인 만으로도 3(m)으로 나누었을 때 나머지가 0인 수를 만족하기 때문에 해당 개수를 그대로 카운트해주는 것이 필요하다.

 

따라서 총 개수는 3 + 3 + 1 = 7가지 경우가 존재한다.

 

 

Python3

import sys
n, m = map(int, sys.stdin.readline().split())
numbers = [0]+list(map(int, sys.stdin.readline().split()))
prepix = [0] * m
for i in range(1, n+1):
    numbers[i] += numbers[i-1]
    prepix[numbers[i] % m] += 1
cnt = prepix[0]
for i in prepix:
    cnt += i*(i-1)//2
print(cnt)