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를 반환한다.