[Greedy][Medium] 55. Jump Game

Q. nums의 계단이 주어질 때, 현재 위치의 nums 값이 해당 위치에서 점프 할 수 있는 계단 수이다. 

이때 마지막 계단에 도달 가능한지 여부를 반환하라. 

 

 

Solution. 

 일단 기본 로직 자체는 큰 복잡함이 없다. 

 특정 위치에서 가능한 모든 위치를 뛰어 본다. 

 그리고 끝에 도달하면 성공 실패 여부를 기록하고, 캐싱한다. 

 처음으로 되돌아와 계속 확인시 이 캐시를 확인한다. 

 

 기본적인 dp 문제다. 

 

 

 bool help(vector<int>& vCache, vector<int>& nums, int idx)
{
    if(idx == nums.size()-1)
        return true;
    if(vCache[idx] >= 0)
        return vCache[idx]==1;

    for(int q = 1; q <= nums[idx]; ++q)
    {
        int nIdx = idx + q;
        if(nIdx >= nums.size()) 
            break;
        if(help(vCache, nums, nIdx))    
        {
            vCache[idx] = 1;
            return true;
        }
    }
    vCache[idx] = 0;
    return false;
}

bool canJump(vector<int>& nums) 
{  
    vector<int> vCache(nums.size(), -1);
    return help(vCache, nums, 0);
}

 

문제는 이 솔루션이 계단 문제의 최적해가 아니라는 것이다. 

계단 문제 최적화는 별도로 다시 알아본다.