LeetCode : 45. Jump Game II

회사에서 교육 듣느라 넘 바빠서 오랜만에 다시 LeetCode 정주행을 시작하려고 한다!

아무래도 문제의 추천수가 많을수록 퀄리티가 높고 좋은 문제라고 생각해서

Top 100 Liked Questions 카테고리에 있는 문제들을 다 풀어보려고 한다.

 

Jump Game || 문제는 Greedy한 아이디어로 풀 수 있는 문제이다.

코드가 짧고 간결하기 때문에 코드를 참고하시면 이해가 빠를 것이라 생각합니다.

 

class Solution {
public:
    int jump(vector<int>& nums) {
        int chk[10001] = {0, };
        bool isReach = false;
        for(int i=0; i<nums.size(); i++)
        {
            for(int j=i+1; j<=i+nums[i]; j++)
            {
                if(chk[j]!=0);
                else chk[j] = chk[i]+1;
                if(j==nums.size()-1)
                {
                    isReach = true;
                    break;
                }
            }
            if(isReach) break;
        }
        return chk[nums.size()-1];
    }
};