[LeetCode] 45. Jump Game II

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

Jump Game II - LeetCode

문제 유형 : 배열

문제 난이도 : Medium

 

문제

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

 

n의 길이를 가진 정수 배열 nums가 있다. 각 값은 점프할 수 있는 거리를 뜻한다. 인덱스 0부터 시작해서 n-1까지 최소한의 점프의 수를 구하게 하시오.

 

풀이

우선, 점프할 수 있는 거리가 아니라, 점프해서 최대 어디까지 갈 수 있는지로 값을 바꾼다.

그 다음 다시 순회하여 n-1까지 닿는 최소 거리를 구한다.

 

코드(C++)

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 idx = 0;
      int ans = 0;

      while(idx < nums.size() - 1)
      {
        ans++;
        idx = nums[idx];
      }

      return ans;
    }
};