[LeetCode] 55. Jump Game

🔗 Problem Link

Jump Game - LeetCode

---

❔Thinking

• 현재의 nums값은 갈 수 있는 최대 칸의 개수를 의미한다.
• nums의 길이가 10000까지이고, nums의 값이 100000까지 이므로, 모든 경로를 탐색할 수 없다.

---

💻Solution

def canJump(self, nums: List[int]) -> bool:
    reachable = nums[0]
    for i in range(len(nums)):
        if reachable < i:
            return False
        else:
            reachable = max(reachable, i+nums[i])
    return True

---

🗝️keypoint

1. 값을 하나씩 확인하면서, 현재보다 더 멀리 갈 수 있는 경우를 찾아 저장한다.
2. 현재의 값보다 작은 값들은, 결국 더 멀리 갈 수 없음을 의미한다.