input :
- nums
output :
- nums[-1]에 도착하기 위한 최소 점프 횟수를 출력하시오.
조건 :
- 초기 위치는 nums[0]
Solution explain : Solution1
idea
- 모든 위치에서 이동할 수 있는 위치를 확인한다. (DP를 활용해서)
- DP는 말만 들으면 맨날 접근하기 어렵다. 차라리 재귀로 먼저 생각을 해보자.
이렇게만 보면 도대체 어떻게 접근을 해야 하나 싶긴 하다. 근데 그림을 보다보니까 계속 idx 2, 3, 4를 중복해서 들어간다. 얘를 저장해놓는 방식으로 가면 그게 DP인 거다.
- 그러므로 dp배열을 하나 만들어 dp[0] = 0로 초기화를 한다. 그 다음부터는 점프의 횟수를 기록하는데 모든 node를 순회하면서 각 step들에 맞게 저장을한다. 말은 장황하지만 그냥 2중 반복문으로 순회를 한다.
- 해설의 미친 접근, 현재 점프를 통해 갈 수 있는 가장 넓은 범위를 만든다. 그리고 그 범위를 트리처럼 쌓는 방식으로 본다면 그 개수를 점프의 횟수로 볼 수 있다.
주의
- 역시 해설을 보고 그림을 그려보는게 이해하기 제일 좋다.
class Solution:
def jump(self, nums: List[int]) -> int:
length = len(nums)
dp = [float("inf")] * length
dp[0] = 0
for idx in range(length):
num_range = nums[idx]
for step in range(1, num_range + 1):
if idx + step >= length:
continue
dp[idx + step] = min(dp[idx] + 1, dp[idx + step])
return dp[-1]
class Solution:
def jump(self, nums: List[int]) -> int:
length = len(nums)
dp = [float("inf")] * length
dp[0] = 0
for idx in range(length):
num_range = nums[idx]
for step in range(1, num_range + 1):
if idx + step >= length:
continue
dp[idx + step] = min(dp[idx] + 1, dp[idx + step])
return dp[-1]