숫자 num과 다른 값 k의 목록이 있다고 가정합니다. 여기서 nums[i]의 항목은 지수 i에 도달하는 비용을 나타냅니다. 인덱스 0에서 시작하여 nums의 마지막 인덱스에서 끝나는 경우. 각 단계에서 우리는 위치 X에서 최대 k 단계 떨어진 위치로 이동할 수 있습니다. 마지막 인덱스에 도달하려면 비용 합계를 최소화해야 하므로 최소 합계는 얼마가 될까요?
따라서 입력이 nums =[2, 3, 4, 5, 6] k =2와 같으면 출력은 12가 됩니다. 2 + 4 + 6을 선택하여 최소 비용 12를 얻을 수 있기 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- ans :=0
- h :=빈 힙
- 0에서 숫자 크기 범위의 i에 대해
- 값:=0
- h가 비어 있지 않은 동안 do
- [val, index] :=h[0]
- 인덱스>=i - k인 경우
- 루프에서 나오다
- 그렇지 않으면
- 힙에서 상단 삭제
- ans :=nums[i] + val
- 힙 h에 쌍(ans, i) 삽입
- 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
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