[medium] 1696. Jump Game VI

문제

https://leetcode.com/problems/jump-game-vi/

Jump Game VI - LeetCode

---

풀이방법

보자마자 DP로 풀어야겠구나 싶었다 (계단 오르기 문제랑 비슷한 유형으로 보여서...)

dp 배열을 -inf 로 초기화하고 각 index에 도달했을 때 최대 score를 dp 배열에 저장해가면서 풀면 된다

dp[n-1] = max(dp[n-1-1], dp[n-1-2], ..., dp[n-1-k]) + nums[n-1]

dp 배열에 초기화 값이 아닌 다른값이 저장되어 있다면, 이미 그 부분은 이전에 연산이 완료 되었다는 의미이기 때문에 건너뛴다

여기까지 생각해서 topdown DP로 풀었더니 시간복잡도가 O(N*k) 라서 시간초과

 

그래서 max heap을 적용해야 한다고 힌트2에 적혀있는데, 방법을 잘 모르겠어서 다른 사람들 풀이보고 따라했다

각 index에서 주변 k개를 전부 탐색하는 시간을 줄이기 위해서 heap에 (maxscore, index)를 저장해두고, 그 중에 최대값만 확인하는 방법을 활용한다

그런데 파이썬의 경우에는 heapq 가 min heap이라서 score에 -를 붙여서 저장하고 계산하다가 마지막에 리턴할때만 -를 다시 붙여서 리턴해주어야 해서 좀 귀찮다

아무튼 그래서 heap 이 자동으로 정렬되서 맨 위에 있는 값이 최소값(= -maxscore)이기 때문에, 이 값이 현재 index에서 k 이내에 있는지만 체크하면서 관리하면 되는 방식이다

반응형

---

코드

### max heap: 시간복잡도 O(N*logk) ###
class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        N = len(nums)
        score = []

        for index in range(N):
            curmax = 0
            if score:
                while score[0][1] < index-k:
                    heapq.heappop(score)
                curmax = score[0][0]
            heapq.heappush(score, (curmax-nums[index],index))

            if index == N-1:
                return -(curmax-nums[index])

### 단순한 topdown DP: 시간복잡도 O(N*k)라서 시간초과 ###
class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        N = len(nums)
        score = [-float('inf')] * N
        
        def dp(index):
            if score[index] != -float('inf'):
                return score[index]
            for i in range(1, k+1):
                if index-i < 0:
                    break
                score[index]  = max(score[index], dp(index-i)+nums[index])
            return score[index]
            
        score[0] = nums[0]
        return dp(N-1)