LeetCode: 45번 (Jump Game II) [JAVA]

문제 링크

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

Jump Game II - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 nums 배열 길이만큼의 dp 배열 생성 (모든 위치의 값을 매우 큰 수로 초기화)
2. 목적지인 배열의 끝은 dp 배열의 값을 0으로 초기화
3. 재귀 기반 탐색 search 함수 생성 (파라미터 배열 속 위치 정보인 index, nums 배열)
   1) 기저 조건으로는 index가 nums 배열 길이를 넘으면 답으로 나올 수 없는 큰 수 리턴
   2) 앞서 해당 index에 대해 dp 속 값이 존재하면 해당 값 반환
   3) 현재의 다음 위치부터 움직일 수 있는 최대 위치까지 중 search() 함수의 결과값이 가장 큰 값 저장
   4) 해당 값 +1 을 dp 배열에 저장하며 반환
4. 0번째 위치에 search() 함수 호출 후 결과값 반환

 문제 자체는 단순한 재귀기반 탐색에 dp를 적용하면 해결할 수 있다. 결국 현재 위치에서 목적지까지 갈 수 있는 방법 중 최소의 방법은 현재의 다음 위치~갈 수 있는 최대 위치까지가 반환하는 횟수 중 최대 +1 이기 때문에, 이를 바탕으로 재귀 함수를 작성한다. 함수의 인자로는 주어진 nums 배열 속 특정 위치를 나타내는 index와 nums배열 그자체를 받으며, 기저조건으로는 index가 nums 배열 길이를 넘어설 때 답으로 나올 수 없는 매우 큰 수를 반환하는 것으로 한다. 그 다음에는 반복문을 통해 현재의 다음 위치~갈 수 있는 최대 위치까지의 값 중 최대값을 저장하고, 해당 값 + 1을 반환하는 방식이다.
 추가로 여기에 연산의 반복을 줄이기 위해 dp를 활용한다. 우선 nums 배열 길이만큼의 dp 배열을 작성하고, 해당 값을 모두 매우 큰 수로 초기화한다. 그 다음 목적지인 배열의 끝 위치에 대해선 0값으로 초기화한다. 그리고 탐색 함수의 앞 뒤로 주어진 index에 대해 dp 배열 속 값이 존재한다면 해당 값을 반환하고, 연산이 끝나고 나면 해당 값을 반환하기 전에 dp 배열에 저장해준다.

 

class Solution {
    int[] dp;//dp 배열

    public int jump(int[] nums) {
        dp = new int[nums.length];
        Arrays.fill(dp, 987654321);
        dp[dp.length - 1] = 0;//목적지의 경우 횟수 0

        return search(0, nums);
    }

    int search(int index, int[] nums){
        if (index >= dp.length) {//인덱스 밖
            return 987654321;
        }

        if (dp[index] != 987654321) {//기존 결과값이 존재한다면
            return dp[index];
        }

        int result = 987654321;

        for (int i = 1; i <= nums[index]; i++) {//갈 수 있는 곳 중 최대
            result = Math.min(result, search(index + i, nums));
        }

        return dp[index] = result + 1;
    }
}

결과