누적합(백준 알고리즘 10986번)

♣ 누적합

누적합은 배열의 일부 구간에 대한 합을 쉽게 구할 수 있는 알고리즘으로, 배열의 값이 변하지 않는다면 누적합 역시 변하지 않는다는 점을 이용한다. 미리 구해둔 누적합을 이용하여 배열 중 특정 구간의 합을 쉽게 구할 수 있다. 미리 구해둔 합을 사용한다는 점에서 DP와 비슷하다. 

 

♣ 1차원 배열에서의 누적합

arr = [1, 2, 3, 4, 5]
arr_sum = [1, 3, 6, 10, 15]

i항부터 j항까지의 부분배열에 대한 누적합 = s[j-1] - s[i-1]
arr_sum 에서 3항부터 5항까지의 부분배열에 대한 누적합 = arr_sum[j-1] - arr_sum[i-1] = arr_sum[4] - arr_sum[2]

 

 

 

♣ 백준 알고리즘 10986번

 

 

위의 문제는 배열이 주어졌을 때, 이 배열에서 합이 M으로 나누어 떨어지는 연속된 부분 구간합의 개수를 구하는 문제이다. 즉 배열에서 구할 수 있는 모든 부분 구간합 중 M으로 나누어 떨어지는 수를 구하는 것이다. 

 

처음에는 배열을 하나씩 늘려가며 M으로 나눠서 구해야 하나 생각했는데 그렇게 하면 분명 시간초과가 나오게 된다.  이중, 삼중 for문을 사용할 필요 없이 한 번의 for문으로 문제를 해결할 수 있다. 

 

원리는 이렇다. 배열 안의 숫자들을 하나씩 더해서 누적합을 만들어가면서 그 안에서 M으로 나눠떨어지는 눈에 보이지 않는 배열들을 구하는 것이다. 

 

[예시] 

arr = [1, 2, 3, 1, 2]
m = 3 (나누는 숫자)

위의 경우에서 누적합이 3으로 나누어떨어지는 부분배열은 아래와 같다. 
[1, 2], [1, 2, 3], [3], [2, 3, 1], [3, 1, 2], [1, 2], [1, 2, 3, 1, 2]

arr의 숫자들을 하나씩 가져와서 누적합을 구하면서 3으로 나누어떨어지는 부분배열을 구한다. 
부분배열은 누적합을 m으로 나눠서 구해지는 나머지로 관리한다. 

count = [0] * 3
count = [0, 0, 0]  => m이 3이므로 나올 수 있는 나머지가 0, 1, 2이다.
answer = 0 => m으로 나눠떨어지는 부분배열의 수 

1) num = 1 , 부분배열로 치면 [1] 
sum(누적합) = 1, 나머지 1 
나머지 1에 해당하는 count의 수를 1 올리기 전에, 이전의 count[1]을 고려한다. 이전값 0이므로 별다른 행위를 하지 않는다. 
count = [0, 1, 0]

2) num = 2, 부분배열 [1, 2]
sum(누적합) = 3, 나머지 0
나머지가 0이므로 answer = 1
count[0]의 수를 1 올리기 전에 이전의 count[0]을 고려한다. 0이므로 별다른 행위 X
count = [1, 1, 0]

3) num = 3, 부분배열 [1, 2, 3]
sum(누적합) = 6, 나머지 0
나머지가 0이므로 answer = 2 

count[0]의 수를 1 올리기 전에 이전의 count[0]을 고려한다. count[0]의 값은 1이다. 즉, 이전에 이미 3으로 나눠지는 누적합을 가진 부분배열([1, 2])이 있었다는 의미이다. 

이전의 부분배열[1, 2]과 현재의 부분배열[1, 2, 3]이 같은 나머지를 가진다는 것은, 현재의 부분배열과 이전 부분배열 사이의 차이에 해당하는 배열의 누적합이 3의 배수라는 뜻이다. 

즉 나머지로 따지면 이전 부분배열의 누적합 arr[i] = 3*A, 현재 부분배열의 누적합 arr[j] = 3*B 이다. arr[j] - arr[i] = 3*(B-A) 이므로, arr[j]와 arr[i] 의 차에 해당하는 부분배열이 3의 배수가 된다는 것이다.

위의 예시에서 보면 [1, 2]와 [1, 2, 3]의 차에 해당하는 부분배열은 [3]이다. [3]의 누적합은 3으로 나누어떨어진다. 그래서 이번에는 현재의 부분배열 [1, 2, 3] 뿐만 아니라 이전의 count[0]에 해당하는 배열과 이번 배열 사이의 3으로 나눠떨어지는 부분배열인 [3]까지 구할 수 있는 것이다.

 

 따라서 

answer += count[0] 에다가 이어서 answer+=1 이 되어서 answer=3이다. 
count = [2, 1, 0]

4) num = 2, 부분배열 [1, 2, 3, 1]
sum(누적합) = 7, 나머지 1

count[1] = 1, 이전의 부분배열은 [1] 이고 현재 부분배열과 이전부분배열 사이의 차이 배열은 [2, 3, 1]이다. 

이 배열의 누적합 역시 3의 배수가 되므로 answer+= count[1] = 4 가 된다. 

count = [2, 2, 0]

5) num = 1, 부분배열 [1, 2, 3, 1, 2]
sum(누적합) = 9, 나머지 0
answer = 5
또한 count[0] = 2이므로 answer+=count[0] = 7

count[0]에 해당하는 이전 배열들은 [1, 2], [1, 2, 3]이다. 현재 배열 [1, 2, 3, 1, 2] 와의 차이 배열은 각각 [3, 1, 2], [1, 2] 이다. 이 배열들은 모두 누적합을 3으로 나눴을 때 나머지가 0이다. 

count = [3, 2, 0]

 

전체 answer = 7 이 된다. 

 

 

♣ 전체 코드

import sys
input = lambda: sys.stdin.readline().rstrip()

n, m = map(int, input().split())
numbers = list(map(int, input().split()))

pre_sum = 0
count = [0] * m
answer = 0

for num in numbers:
    pre_sum += num
    remainder = pre_sum % m
    if remainder == 0:
        answer += 1
    answer += count[remainder]
    count[remainder] += 1

print(answer)

 

 

♣ 참고 자료

https://code-angie.tistory.com/22

[알고리즘 / Python] 누적합 (Prefix Sum)

https://velog.io/@tnfls99/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-PYTHON-%EB%88%84%EC%A0%81%ED%95%A9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98