1. 문제
임의의 자연수로 이루어진 수열(nums)이 있을 때, 특정 간격(k) 이상으로 떨어지지 않도록 연속되게 수들을 선택하여 그 합이 최소가 되게 하는 부분 수열(result)을 구해보자.
2. 준비물
임의의 수열(array) : nums
넘으면 안 되는 간격(int) : k = 2
index를 관리할 deque : dq
조건을 만족하는 최소값을 관리할 dp테이블 : dp
부분 수열을 구할 배열(array) : sub
3. 해결 방법
가. 아이디어
i번째 수까지의 최적해를 dp[i]라고 했을 때, dp[i]는 dp[i-k-1] ~ dp[i-1] 중 최소값에 i번째 수를 더한 값입니다.
식으로 쓰면 아래와 같습니다.
\( dp[i] = \min \limits _{j = i-k-1} ^{i-1} dp[j] \)
그리고 위 수식을 더 효율적으로 탐색할 수 있는 방법이 있습니다.
(i-k-1)번째 부터 (i-1)번째 까지의 값을 아래와 같이 시각적으로 표현했을 때를 생각해봅시다.
i번째 수의 탐색이 끝나고 (i+1)번째 수의 탐색이 시작될 때, 하나하나씩 맨 앞의 dp값은 볼 필요가 없어집니다.
그래서 앞쪽에 뒤쪽보다 더 큰 값이 있다면, 언젠가 맨 앞쪽으로 사라질 때까지 절대 선택될 일이 없습니다.
따라서 새로운 값이 추가될 때, 뒤 쪽부터 차례로 살펴보면서 자신보다 큰 값은 미리 제거해두면 이후에 다시 살펴보지 않아도 되므로 효율적입니다.
나. 과정
1) nums의 맨 앞에 0을 추가합니다. 그리고 deque에 인덱스 0을 추가합니다.(초기화)
2) 다음 과정을 반복합니다.
이전 인덱스 값을 sub에 저장합니다. i번째의 최적해(누적합)를 dp테이블에 저장합니다.
deque가 오름차순(monotonic)을 유지하도록 오른쪽에서 dp[i]보다 큰 dp 인덱스 값을 모두 제거합니다. 그리고 i를 오른쪽에 추가합니다.
deque에 관리되는 인덱스의 범위가 (i-k-1) ~ (i-1) 이 되도록 범위를 벗어나는 인덱스 값을 왼쪽에서 모두 제거합니다.
3) 모든 과정을 마치면 deque의 맨 앞에 있는 인덱스가 우리가 찾는 subsequence의 마지막 인덱스입니다.
이 인덱스로 sub 배열의 값을 찾으면, 바로 이전의 인덱스를 알 수 있습니다.
반복하여 따라가면 0, 3, 5, 6, 9 인덱스라는 것을 알 수 있습니다.
0은 초기값이었으므로 제외하고, 3, 5, 6, 9번째 값을 찾으면 {0, 0, 2, 1}이라는 subsequence를 구할 수 있습니다.
4. 소스 코드
from collections import deque
N, k = 9, 2
nums = [0] + [1, 5, 0, 1, 0, 2, 7, 3, 1]
dp = nums[:]
sub = [0] * (N+1)
dq = deque([0])
for i in range(1, N+1):
sub[i] = dq[0]
dp[i] = dp[dq[0]] + nums[i]
while dq and dp[i] <= dp[dq[-1]]:
dq.pop()
while dq and dq[0] < i-k:
dq.popleft()
dq.append(i)
res = []
i = dq[0]
while i != 0:
res.append(nums[i])
i = sub[i]
print(*res[::-1])
# 0 0 2 1
