백준 11060 자바 - 점프 점프 (BOJ 11060 JAVA)

문제 : boj11060

 

  N이 1000까지이고, Ai가 최대 100이라 대충 돌려도 O(NA = 100000) 이라 널널한 문제이다. 가장 좌측지점부터 시작해서 dp 개념을 살짝 섞은 브루트포스로 풀면 된다.

 

  각 입력값에서 갈 수 있는 모든 곳을 가보면서 최소로 갈 수 있는 수치로 갱신해가면 된다. dp[x]는 x위치까지 갈 수 있는 최소 점프 횟수가 된다. 점화식은 Ai에서 i=x에서 시작해 우측으로 이동한 경우이고 현재 y (x+1 <= y <= x+Ax) 를 보고 있다면, dp[y] = min(dp[y], dp[x]+1)

 

  예를들어 예제 입력 1은 다음과 같이 구해볼 수 있다.

 

1. 시작은 다음과 같다. dp는 최소 횟수 계산을 위한 배열이다. 가장 좌측이 시작점이므로 0으로 시작한다. 나머지는 무한대이다.

 

2. i=1일 때 A_1이 1 이므로 우측으로 1칸까지 갈 수 있다. 마찬가지로 다음 A_2에서는 2칸을 갈 수 있다. 거기까지 dp 배열을 써보면 다음과 같다. 이런식으로 점화식을 적용해가며 i를 1씩 증가해가며 기입하면 된다.

 

3. 이 때 현재 상황까지 확인해보자. A_5에서 우측으로 3칸에 4를 써두었다. A_6에서 우측으로 2칸을 갈 수 있는데, 그럼 5를 기입해야되는데 이미 A_5에서 점프한 횟수가 더 작다. 따라서 갱신하지 않는다.

 

4. 이런식으로 모두 써보면 다음과 같다. 최종적으로 dp[N]인 dp[10]=5가 답이다.

 

 

코드 : github

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

public class Main {
    private static final int MAX = 1001;

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n+1];
        for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(st.nextToken());

        int[] dp = new int[n+1];
        Arrays.fill(dp, MAX);
        dp[1] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i+1; j < i+1+arr[i]; j++) {
                if (j > n) break;
                dp[j] = Math.min(dp[i]+1, dp[j]);
            }
        }

        System.out.println(dp[n]==MAX?-1:dp[n]);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}