[Leetcode] 45. Jump Game II 문제 풀이

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

Jump Game II - LeetCode

 

문제 내용

몇 번만에 점프해서 끝지점 까지 오는지 최소 값을 구하는 문제

 

Example 1:

Input: nums = [2,3,1,1,4]

Output: 2

Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

 

문제 풀이

DP를 사용해서 풀었다.

dp[n] = n에서 갈 수 있는 최대 index

이 식으로 index를 점프하면서 몇번 했는지 구했다.

 

class Solution {
public:
    int jump(vector<int>& nums) {
        for (int i = 1; i < nums.size(); ++i) {
            nums[i] = max(nums[i] + i, nums[i-1]);
        }
        
        int cnt = 0;
        int i = 0;
        while(i < nums.size()) {
            if (i >= nums.size()-1) {
                break;
            }
            i = nums[i];
            cnt++;
        }
        
        return cnt;
    }
};