55. Jump Game

• array의 크기가 매우 크고 (10^4) 경우의 수가 많기 때문에 frog jump와 같이 bfs 방식을 사용할 수 없다.

• 현재 위치에서 최대로 jump 할 수 있는 길이(maxJump)를 계산한다.
• maxJump는 한 칸을 이동할 때 마다 감소한다.
• 그리고 현재 위치에서 뛸 수 있는 거리가 더 크다면 그 값을 maxJump로 한다.

• maxJump가 0 미만이 되면 더 이상 앞으로 전진할 수 없는 상황으로 판단(false)한다.

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int end = nums.size() - 1;
        int maxJump = 0;
        for (int pos = 0; pos < end; ++pos) {
            int jump = nums[pos];
            if (jump > maxJump) {
                maxJump = jump;
            }
            --maxJump;
            if (maxJump < 0) return false;
        }
        return true;
    }
};