LeetCode - 45. Jump Game II

문제

문제 : 45. Jump Game II
문제는 nums[0]에서 j만큼 점프할 수 있고( nums[i + j] ) 최소한의 점프로 nums[i-1]에 도달하는 경우의 수를 구한 후 점프 횟수를 반환하는 것이다.
조건은 다음과 같다.

• 1) 0 <= j <= nums[i]
• 2) i + j < n

풀이

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumpCnt = [0] * len(nums)
        for i in range(len(nums)):
            for j in range(1, nums[i]+1): # 0 <= j <= nums[i]
                if i + j >= len(nums):
                    break
                if jumpCnt[i + j] == 0 or jumpCnt[i+j] > jumpCnt[i] + 1:
                    jumpCnt[i + j] = jumpCnt[i] + 1
        return jumpCnt[-1]

• for j in range(1, nums[i]+1)에서 0부터 시작하지 않은 이유는 0은 제자리 점프기 때문에 1부터 시작하도록 했다.
• 내가 생각하는 이 코드의 핵심이다.

 if jumpCnt[i + j] == 0 or jumpCnt[i+j] > jumpCnt[i] + 1:
     jumpCnt[i + j] = jumpCnt[i] + 1

• 현재위치 i에서 점프할 위치인 i + j의 값이 0이면 jumpCnt[i+j]는 점프할려는 위치의 값 + 1을 해주면 된다.
• 각 배열에는 해당 위치까지 오는데 필요한 점프 횟수가 jumpCnt 배열에 저장되어있기때문에 jumpCnt[i] + 1의 값을 jumpCnt[i + j]에 할당해주는 것이다.
• 그리고 점프할 위치인 jumpCnt[i+j]값이 0이아닌경우에는 jumpCnt[i+j]값보다 jumpCnt[i] + 1의 값이 작은 경우엔 junpCnt[i+j]값을 바꿔준다.

메모

• DP 사용