문제 개요
숫자로 이루어진 리스트 nums와 정수 k가 주어집니다. 이때 nums[i]는 인덱스 i에 착지했을 때 발생하는 비용을 의미합니다. 우리는 인덱스 0에서 출발하여 리스트의 마지막 인덱스에 도달해야 하며, 각 단계에서 현재 위치 X로부터 최대 k칸 떨어진 어떤 위치로든 점프할 수 있습니다.
목표는 마지막 인덱스에 도달하기 위해 지불해야 하는 비용의 합을 최소화하는 것입니다. 그렇다면 최소 비용은 얼마일까요?
예시
입력이 다음과 같다고 가정해 보겠습니다.
- nums = [2, 3, 4, 5, 6]
- k = 2
이 경우 출력은 12가 됩니다. 인덱스 0, 2, 4를 순서대로 밟아 비용 2 + 4 + 6 = 12로 마지막에 도달하는 것이 가장 저렴한 경로이기 때문입니다.
풀이 접근 방식
이 문제는 동적 계획법(DP)과 최소 힙(Min Heap)을 조합하여 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 각 위치 i에 대해, 해당 위치까지 도달하는 최소 누적 비용을 계산합니다.
- 현재 위치에서 점프 가능한 범위는 이전 k개의 위치뿐이므로, 힙을 활용해 범위 내에서 가장 작은 누적 비용을 빠르게 조회합니다.
- 범위를 벗어난 오래된 항목은 힙에서 제거하여 슬라이딩 윈도우처럼 관리합니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- ans := 0으로 초기화
- h := 빈 힙 생성
- i를 0부터 nums의 크기까지 반복:
- val := 0으로 초기화
- 힙 h가 비어 있지 않은 동안 반복:
- [val, index] := 힙의 최상단 요소
- 만약 index >= i - k라면 (점프 가능 범위 내라면) 반복 종료
- 그렇지 않다면 힙 h에서 최상단 요소 제거
- ans := nums[i] + val
- (ans, i) 쌍을 힙 h에 삽입
- ans 반환
이 방식의 시간 복잡도는 O(n log n)으로, 모든 경로를 탐색하는 완전 탐색(O(k^n))보다 훨씬 효율적입니다.
파이썬 구현 예제
아래 코드를 통해 실제 구현을 확인해 보겠습니다.
from heapq import heappush, heappop
class Solution:
def solve(self, nums, k):
ans = 0
h = []
for i in range(len(nums)):
val = 0
while h:
val, index = h[0]
if index >= i - k:
break
else:
heappop(h)
ans = nums[i] + val
heappush(h, (ans, i))
return ans
ob = Solution()
nums = [2, 3, 4, 5, 6]
k = 2
print(ob.solve(nums, k))실행 결과
입력
[2, 3, 4, 5, 6], 2
출력
12
정리
이 문제는 계단 오르기 유형의 최소 비용 문제에 점프 거리 제한이 추가된 형태입니다. 힙을 사용하면 매번 이전 k개 위치의 최솟값을 일일이 확인하지 않고도 로그 시간에 조회할 수 있어 전체 성능이 크게 향상됩니다. 슬라이딩 윈도우 최솟값 문제에서는 덱(deque)을 활용한 O(n) 풀이도 가능하니, 참고로 학습해 보시길 권장합니다.