[Greedy][Medium] 45. Jump Game II

https://leetcode.com/problems/jump-game-ii/description

 

Q. nums의 계단이 주어진다. 이때 nums.size()-1 의 계단에 도달하려고 한다. 

계단은 nums[i] 위치에서 0 ~ nums[i] 위치만큼 뛸 수 있다. 

이때 도달가능한 최소 단계수를 구하라. 

 

 

Solution. 

 DP 에서 많이 보이는 계단 jump 문제다. 

 수식을 잘 세우면 어려울 것이 없다. 

 

특정 계단에 도달해서 0 ~ 현재 값 까지 점프 가능하다. 

0 이면 점프하지 않으므로 1 부터점프하고, 

도달하려는 다음 계단이 전체 nums 의 크기를 넘으면 하지 않는다. 

 

이 단계수를 더하고 그 중 최대를 찾는다. 

 

로직대로 코드를 만든다. 

 

 int helper(vector<int>& vCache, vector<int>& nums, int idx)
{
    if(idx == nums.size()-1)
        return 0;

    if(vCache[idx] >= 0)
        return vCache[idx];

    int ret = INT_MAX;
    for(int q = 1; q <= nums[idx]; ++q)
    {
        if(idx+q >= nums.size())
            break;

        int ans = helper(vCache, nums, idx + q);
        if(ans != INT_MAX)
            ret = min(ret, 1 + ans);
    }
    return vCache[idx] = ret;
}

int jump(vector<int>& nums) 
{
    vector<int> vCache(nums.size(), -1);
    return helper(vCache, nums, 0);
}

 

 

문제는 직관과 기본 풀이법에 근거해 풀었는데, 

기대 이하의 rumtime speed가 나온다는 것이다. 

 

추후에 최적화에 대해 다시 살펴 보기로 한다.