[DP/자바] 코드트리 IL. 최대 점프 횟수

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 해석

내가 얻고자 하는 값은, 문제에서 주어진 규칙을 따를 때 "첫 번째 위치에서부터 최대 몇 번의 연속된 점프를 할 수 있는가?" 이다.

수열 위의 임의의 점 arr[i]이 갖는 값은 그 위치에서 얼마만큼 멀리 점프를 할 수 있는지를 의미하며, 무조건 적게 뛰거나 많이 뛴다고 해서 최선이 아니므로 그리디는 부적절한 것으로 보인다.

그렇다면 전체 경우의 수를 탐색해야 하는가? n의 크기가 1,000이하이므로 백트래킹이나 루프를 이용한 완전탐색을 돌리려고 시도하면 어림짐작 하더라도 상당히 많은 경우의 수를 탐색해야 한다. 따라서 이 또한 부적절하다.

 

특정 위치에서 누적된 점프 수의 최대를 dp[i]에 저장한다고 할 때, 인덱스 j를 0부터 i 미만까지 순회하여 j + arr[j]의 값이 i보다 크거나 같을 경우는 j 인덱스에서 i인덱스까지 점프할 수 있는 것이니, 다음과 같은 점화식을 세울 수 있다. 이렇게 풀어내면 2차원 루프만으로 원하는 값을 도출할 수 있으므로, 동적계획법이 적절한 접근일 것이다.

 dp[i] = Math.max(dp[i], dp[j]+1);

 

 

문제 풀이

이 문제의 포인트는, '첫 번째 위치에서부터' 얼마나 많이 점프할 수 있는가이다. 따라서 중간에 점프가 끊기는 부분(dp[i] == 0)이 있다면 그 이후부터는 dp의 값들을 고려하지 않아도 된다. 이를 감안하여 코드를 설계하면 다음과 같이 나온다.

package 코드트리.DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 최대_점프_횟수 {
    private static int n;
    private static int[] arr;
    private static int[] dp;
    private static int ans = 0;

    public static void main(String[] args) throws IOException {
        init();

        // dp 배열 타뷸레이션
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if ((j + arr[j]) >= i) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        
        // 첫번째 위치부터 연속되는 점프 값 중 최대 구하기
        for (int i = 1; i < n; i++) {
            if (dp[i] == 0) {
                break;
            }
            ans = Math.max(dp[i], ans);
        }
        System.out.println(ans);
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        arr = new int[n];
        dp = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] = 0;
        }
    }
}