[LeetCode][Python3] 55. Jump Game

Problem :

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

My Solution :

class Solution:

def canJump(self, nums):

"""

:type nums: List[int]

:rtype: bool

"""

M = 0

for n in nums[:-1]:

M = max(M-1, n)

if M == 0:

return False

return True

Comment :

나의 전략은 다음과 같다.

M : 현재 위치에서 전진할 수 있는 칸의 수를 의미. 즉 연료라고 생각하자. 직전 M에서 1을 감소시킨 값과 (한 칸 전진해 왔으니) 현재 위치의 값 중 최댓값을 선택한다.

만약 M이 0이면 (연료가 떨어지면) 더 이상 전진할 수 없다. 하지만 마지막 칸에서는 M이 0이어도 상관이 없다. 따라서 마지막 칸은 제외하고 진행을 한다. 중간에 M이 0이 되면 False를 반환한다. 무사히 순회하면 True를 반환한다.