문제 개요
숫자로 이루어진 리스트 stairs와 정수 k가 주어진다고 가정해 보겠습니다. 현재 우리는 0번째 계단에 서 있으며, 마지막 인덱스의 계단까지 올라가야 합니다. 여기서 stairs[i]는 i번째 계단에 도달할 때 드는 비용을 의미하며, 한 번에 1칸부터 k칸까지 자유롭게 점프할 수 있습니다. 목표는 마지막 계단에 도달하는 최소 비용을 구하는 것입니다.
예를 들어, stairs = [4, 11, 11, 3, 2]이고 k = 3이라면 결과값은 9가 됩니다. 비용이 4, 3, 2인 계단만 밟고 올라가면 총 9의 비용으로 정상에 도달할 수 있기 때문입니다.
해결 전략: 모노토닉 덱 활용
이 문제는 동적 계획법(DP)으로도 풀 수 있지만, 단순 DP는 각 계단마다 이전 k개 계단을 모두 확인해야 하므로 O(n×k)의 시간이 소요됩니다. 대신 슬라이딩 윈도우 최솟값 기법과 모노토닉 덱(Double-ended Queue)을 사용하면 O(n) 시간 복잡도로 최적화할 수 있습니다.
핵심 아이디어는 다음과 같습니다. 덱에는 (누적 비용, 인덱스) 쌍을 저장하되, 덱 안의 비용 값이 항상 오름차순을 유지하도록 관리합니다. 그러면 덱의 맨 앞 요소가 항상 현재 윈도우 범위 내의 최소 비용이 됩니다.
알고리즘 단계
덱(deque)을 하나 생성하고, 초기값으로 (stairs[0], 0) 쌍을 삽입합니다.
i를 1부터 stairs의 길이 - 1까지 반복합니다:
현재 인덱스 i에서 점프 거리 k를 벗어난 항목(i - q[0][1] > k)이 있다면 덱의 앞쪽에서 제거합니다.
curcost를 q[0][0] + stairs[i]로 계산합니다. 즉, 현재 윈도우의 최소 누적 비용에 현재 계단의 비용을 더합니다.
덱이 비어 있지 않고 curcost가 덱 마지막 항목의 비용보다 작거나 같은 동안, 덱의 뒤쪽 항목을 제거합니다. 더 큰 비용의 항목은 앞으로 최솟값이 될 수 없기 때문입니다.
(curcost, i) 쌍을 덱의 끝에 삽입합니다.
반복이 끝나면 덱 마지막 항목의 첫 번째 값(q[-1][0]), 즉 마지막 계단의 최소 누적 비용을 반환합니다.
파이썬 구현 코드
from collections import deque
class Solution:
def solve(self, stairs, k):
q = deque([(stairs[0], 0)])
for i in range(1, len(stairs)):
while i - q[0][1] > k:
q.popleft()
curcost = q[0][0] + stairs[i]
while q and curcost <= q[-1][0]:
q.pop()
q.append((curcost, i))
return q[-1][0]
ob = Solution()
stairs = [4, 11, 11, 3, 2]
k = 3
print(ob.solve(stairs, k))입력
[4, 11, 11, 3, 2], 3
출력
9
정리
이 알고리즘은 각 계단을 정확히 한 번씩 처리하므로 시간 복잡도는 O(n)이며, 덱에는 윈도우 크기에 해당하는 최대 k+1개의 항목만 유지되므로 공간 복잡도 역시 O(k)로 효율적입니다. 슬라이딩 윈도우 최솟값 패턴은 이 외에도 다양한 최적화 문제에서 활용되는 강력한 기법이니 꼭 익혀두시기 바랍니다.