55 Jump Game

 

Jump Game - LeetCode

배열의 i번째 위치에 도달할 수 있다면 i 이전의 모든 위치를 지날 수 있다는 점을 이용하면 간단하게 풀 수 있다.

솔직히 그냥 위 생각만 가지고 의식의 흐름으로 대충 풀었을 때 그냥 풀리는 수준의 난이도라

개인적으로 왜 Easy가 아니고 Medium인지 이해가 안 되는 문제였다.

 

class Solution {
public:
    vector<bool> check;
    vector<int> vec;
    bool jump(int idx) {
        if (idx >= check.size() - 1 || vec[idx] + idx >= check.size() - 1){
            return true;
        }
        check[idx] = true;
        bool res = false;
        for(int i = vec[idx]; i > 0 && res == false; --i) {
            if (check[idx + i] == false) {
                res = jump(idx + i);
            }
        }
        return res;
    }
    bool canJump(vector<int>& nums) {
        check.resize(nums.size());
        vec = nums;
        return jump(0);
    }
};