[LEETCODE 150] - 55 Jump Game

LeetCode의 55번 문제인  "Jump Game" 문제이다.

 

이문제는 Dynamic Programming 알고리즘을 활용해서 풀어봤다.

https://jyu-seo.tistory.com/98

09 - Dynamic Programming

 

각 칸에서 점프해서 마지막 칸까지 도달할수 있는지 체크하는 문제이다. DP[i]를 i번째 칸에서 최대로 점프 할 수 있는 칸 수라고 할때 DP[i] = max(DP[i-1] - 1, nums[i])로 구할 수 있다. 즉, 이전 칸에서 최대로 점프하거나, 현재 칸에서 최대로 점프하는 경우 중 큰 값이 현재 칸에서 최대로 점프할 수 있는 칸 수가 된다. 이때 새로운 배열을 할당하기 보다, 기존 배열의 값을 최대 값으로 갱신할 수 있다.

 

정답코드

class Solution:
     def canJump(self, nums: List[int]):
        if len(nums) > 1 and nums[0] == 0:
            return False
        for i in range(1, len(nums) -1):
            nums[i] = max(nums[i], nums[i-1] - 1)
            if nums[i] == 0:
                return False
        return True

 

풀이 해석

1. 배열 길이가 2 이상인데 첫 칸이 0이면, 시작부터 한 칸도 못 움직여서 무조건 실패.

2. 단, 길이가 1이면 이미 마지막 칸에 있으니 이 조건에 걸리지 않음(그래서 True로 가게 됨)

if len(nums) > 1 and nums[0] == 0:
	return False

 

3. 1칸부터 마지막 바로 전 칸 까지 검사.

4. 마지막 칸은 "도달만 하면 끝"이라, 마지막 칸 자체의 점프력이 0이어도 상관 없어서 굳이 검사 안해도됨.

for i in range(1, len(nums) -1):

 

5. nums[i-1]은 이미 갱신 되어 있다면 i-1 칸에 도착했을때의 남은 원료,

 - i로 한 칸 이동하면 연료는 1 줄어서 nums[i-1] - 1

- 그런데 i 칸에 원래 적혀 있던 점프값 nums[i]도 "i에서 새로 얻을수 있는 연료" 로 볼 수 있음

- 따라서 i에서 가능한 최대 연료는

• 이전 칸에서 이어받은 연료(-1) vs 현재 칸이 제공하는 연료
• 둘 중 큰 값

nums[i] = max(nums[i], nums[i-1] -1)

 

6. i에 도착했는데 남은 연료가 0이면, 다음 칸으로 못감.

- 그런데 우리는 마지막 칸 바로 전까지 검사중이니까, 여기서 0이면 마지막 칸까지 갈 길이 남아있는데 멈춘것 -> False

-중간에 막히지 않고 마지막 전 칸 까지 왔으면, 마지막 칸은 한 칸만 가면 되거나 이미 도달 가능 범위 안에 있다는 뜻이므로 True.

if nums[i] == 0:
	return False
 return True

 

짧은 예시

[2, 3, 1, 1, 4]

• i=1: nums[1]=max(3, 2-1=1)=3 (연료 3)
• i=2: nums[2]=max(1, 3-1=2)=2 (연료 2)
• i=3: nums[3]=max(1, 2-1=1)=1 (연료 1)
• 마지막 칸(4)은 검사 안 하지만, i=3에서 연료 1이니 4로 도달 가능 → True