[JAVA/LeetCode] Top 100 Liked Question: 45. Jump Game II

👀 문제

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

👊 도전

1. 설계

1. DP를 이용한다.
2. i 위치에서 건너뛸 수 있는 max를 구하고, 1~max까지 뛰어본다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 *
 * @author HEESOO
 *
 */
class Solution {
    public int jump(int[] nums) {
        if(nums.length==0) return 0;
        
        int[] dp=new int[nums.length];
        Arrays.fill(dp, Integer.MAX_VALUE); // Math.min을 사용하기 위함
        dp[0]=0;
        for(int i=0;i<nums.length;i++){ // i 위치에서 다 체크
            for(int j=1;j<=nums[i] && i+j<nums.length;j++){ // 1부터 nums[i]까지 뛰어본다, 단 배열 범위 벗어나지 않는 범위내에서
                dp[i+j]=Math.min(dp[i+j], dp[i]+1); // 기존 점프 횟수와 i에서 뛴 것 중 작은 값 선택
            }
        }
        
        return dp[nums.length-1];
    }
}

3. 결과

🤟 성공 🤟
처음에는 BFS로 문제를 코드를 작성했는데, 특정 테케에서 시간 초과로 다른 사람의 코드를 참고했다. 뭔가 DP 느낌은 들었는데 점화식이 떠오르지 않았다.

4. 설명

1. DP를 이용한다
   • nums 개수 만큼 dp를 만든다.
   • Math.min()을 이용하여 둘 중 작은 값을 넣을 것이기 때문에 dp가 0으로 초기화 되어있으면 안된다. 따라서 Integer.MAX_VALUE로 min을 통해 값이 무조건 변경되도록 한다.
   • i는 dp에서 확인할 위치이다.
   • j는 i에서 1부터 nums[i]번 만큼 뛸 수 있는 경우다. 예를 들어 [2,3,1,1,4]에서 0번째 인덱스에서는 1부터 2까지 뛸 수 있다.
   • 따라서 j는 1부터 nums[i]만큼 뛰어보는데, 이때 i+j가 배열 범위를 벗어나면 안된다.
   • dp[i+j]는 i위치에서 j만큼 뛴 곳이다. 이곳의 값은 기존 dp[i+j]를 유지하거나, i에서 j만큼 뛰어 해당 위치에 가는 두 방법이 있다. 따라서 dp[i]+1과 기존 dp[i+j] 중 작은 값을 택한다.
   • dp[마지막 위치]에는 인덱스 0부터 뛴 경우를 다 체크하고 min값이 들어갈 것이므로, 해당 값을 리턴하면 된다.

👏 해결 완료!