문제를 본 날: 2022년 11월 5일 오후 5:10 (GMT+9)

문제를 푼 날: 2022년 11월 5일 오후 7:13 (GMT+9)

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

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

Solution

결국에는 가장 마지막에 도달해야하므로 마지막에서 출발해서 처음 출발지점까지 이동한다.

이동하면서 현재 위치(i)에서 최대로 이동할 수 있는 지점(i + nums[i]) 이내에 도착지점으로 갈 수 있는 최근 지점(recent)이 있는지 확인하고 참이라면 최근 지점(recent)를 현재 위치(i)로 업데이트한다.

class Solution {
public:
    bool canJump(vector<int>& nums) {
        const int n = nums.size();
        int recent = n-1;
        
        for(int i=n-2;i>=0;--i){
            if(i + nums[i] >= recent){
                recent = i;
            }
        }
    
        return recent == 0;
    }
};