LeetCode : 55. Jump Game

은근히 코드는 쉬운데,,,, 나는 Greedy문제가 왜 이렇게 어려울까.....?ㅎㅎ

생각만 잘 할 수 있다면 쉽게 구현할 수 있는 Greedy 문제였다.

 

[메인로직]

중요한 부분은! 이 문제는 앞에서부터 해결하려고 하면 복잡해지고 늪에 빠져버린다...(마치 나처럼^^)

뒤에서 부터 접근해보면 생각보다 쉽다!

현재 idx(i)와 현재 갈 수 있는 이동 거리(nums[i])를 더한 값이 반드시 도달해야하는 지점(lastPos)보다 크거나 같다면

현재 내 위치가 다시 lastPos가 되는 것이다. (=> 즉, 내 지점까지만 오면 내가 알아서 마지막 idx까지 도착할 수 있다는 것)

 

class Solution {
public:
    bool canJump(vector<int>& nums) {
        // 현재 위치에서 최대 이동거리만큼 더한 값(i+nums[i])이 마지막 위치(lastPos)까지 도달할 수 있는 지를 판단!
        int lastPos = nums.size()-1; 
        for(int i=nums.size()-1; i>=0; i--){
            if(i+nums[i]>=lastPos){ // 현재 위치가 lastPos까지 도달할 수 있기 때문에 현재위치가 lastPos가 된다.
                lastPos = i;
            }
        }
        
        if(lastPos==0){
            return true;
        }
        
        return false;
    }
};