꿀잠

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

다음 인덱스까지 배열의 현재 값만큼 점프할 수 있을 때 몇번의 스텝으로 최종위치에 도달할 수 있는지에 대한 문제이다. 현재 점프할 수 있는 위치에서 점프 가능한 곳의 최소 값을 dp 배열에 저장하여 해결하였다.

import java.util.*;  
  
public class Solution {  
    public int jump(int[] nums) {  
        int n = nums.length;  
        int[] dp = new int[n];  
        Arrays.fill(dp, Integer.MAX_VALUE);  
        dp[0] = 0;  
  
        for(int i = 0; i < n; i++){  
            int jump = nums[i];  
            int step = dp[i] + 1;  
            int jumpMax = Math.min(i + jump, n - 1);  
            for(int j = i; j <= jumpMax; j++){  
                dp[j] = Math.min(dp[j], step);  
            }  
        }  
  
        return dp[n - 1];  
    }  
}

하지만 이 문제는 그리디 카테고리에 있는 알고리즘 문제이기에 그리디 방식으로 푸는 방식이 궁금해졌다. 다른 솔루션을 찾아 보니 그리디 방식의 경우 핵심 아이디어는 점프한 곳에서 다음 점프 시 가장 먼 곳으로 점프할 수 있는 곳 인지이다. 가장 먼 곳으로 점프하는 경우는 그 이전 구간도 전부 점프할 수 있으므로 점프 가능성을 최선의 선택으로 고르는 그리디 알고리즘이었다. 확인한 솔루션은 아래와 같다.

class Solution {  
    public int jump(int[] nums) {  
        return stepsToJumpFrom(nums, 0);  
    }  
  
    private int stepsToJumpFrom(int[] nums, int start) {  
        if (start >= nums.length - 1) {  
            return 0;  
        }  
        if (start + nums[start] >= nums.length - 1) {  
            return 1;  
        }  
        int furthestReachableNext = -1;  
        int nextStart = start;  
        for (int i = start + 1; i <= start + nums[start]; i++) {  
            if (i + nums[i] > furthestReachableNext) {  
                furthestReachableNext = i + nums[i];  
                nextStart = i;  
                if (furthestReachableNext >= nums.length - 1) {  
                    break;  
                }  
            }  
        }  
        return stepsToJumpFrom(nums, nextStart) + 1;  
  
    }  
}