LeetCode/ Jump Game

0번째 인덱스부터 세려고 하면 어렵다. dp 적용하기도 어렵고. 차라리 거꾸로 적용하면 편하다.

2 3 1 1 4 를 예시로 보면 4부터 시작해서 3까지 거꾸로 간다.

1. 4 + 4 >= 4 이므로 target은 4

2. 1 + 3 >= 4 이므로 target은 3

2. 1 + 2 >= 3 이므로 target은 2

3. 1 + 1 >= 2 이므로 target은 1

4. 2 >= 1 이므로 return true

일련의 과정에서 알 수 있듯이 target까지만 어떻게든 도달한다면 index의 끝까지 도달할 수 있다.

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