백준 11060: 점프점프 [Java] - 포포

문제

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.

출력

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

예제 입력 1 

10 
1 2 0 1 3 2 1 5 4 2

예제 출력 1

5

https://www.acmicpc.net/problem/11060

---

10 
1 2 0 1 3 2 1 5 4 2

예제로 설명을 하자면, 10칸이 주어지고 각 칸에서 점프뛸 수 있는 거리는 1, 2, 0, 1 ... 이렇게 주어진다.

dp[i]는 i번째 칸 까지 도달하는데 점프한 최솟값을 나타내야 한다.
dp[1] = 1번째 칸(맨 첫번째 칸)에 도달하는데 필요한 점프의 횟수이므로, 0으로 설정한다. 시작점이니까.

위의 예제처럼 1번 칸에서는 1만큼 점프를 뛸 수 있다면
dp[1+1] = dp[1] + 1 = 1 로 구할 수 있다. 즉, 2번 칸까지 가는데에 필요한 최소 점프 수는 1이다.

두번째 칸에서는 2만큼 점프를 뛸 수  있는데,
dp[2+1] = dp[2] + 1 = 2
dp[2+2] = dp[2] + 1 = 2
2칸을 뛸 수 있으므로 dp[2+1], dp[2+2]를 최솟값으로 갱신해줘야 한다. 
즉 3, 4번 칸까지 도달하는데에 필요한 최소 점프 수는 2다.

점화식을 도출해보면, 

        Arrays.fill(dp, Integer.MAX_VALUE); 
        
        dp[1] = 0; // 시작점은 점프를 0번하므로 0으로 설정
        
        for (int i = 1; i <= n; i++) {
            // 이전 발판에서 점프 길이가 안되어 갱신이 안 된 칸인 경우
            // --> -1을 출력한다.
            if (dp[i] == Integer.MAX_VALUE) {
                continue;
            }
			
            // nums[i]에 i+1부터 i+nums[i] 블록까지 최솟값으로 갱신해준다.  
            for (int j = 1; j <= nums[i]; j++) {
                dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
            }
        }

만약 점프를 하면서 가는 와중에 모든 발판이 0이라 더이상 나아갈 수 없다면
그 순간부터 dp[i]의 값은 Max_VALUE일 것이다(최솟값으로 갱신을 할 수가 없다)
즉 nums[n] 발판에 도착할 수 없는 경우이므로, dp[n]이 MAX_VALUE인 경우 -1을 출력하면 된다. 

 

dp 배열의 크기를 1101로 초기화 하였는데,
문제의 조건 중 최대 1000 칸까지 입력받을 수 있고
마지막 칸에서 최대 점프 거리인 100 칸을 점프할 수 있기 때문이다.
안그러면 ArrayOutOfIndex뜸

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

public class Main {
    static int n;
    static int[] nums;
    static int[] dp;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        nums = new int[n + 1];
        dp = new int[1101];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[1] = 0;
        for (int i = 1; i <= n; i++) {
            if (dp[i] == Integer.MAX_VALUE) {
                continue;
            }

            for (int j = 1; j <= nums[i]; j++) {
                dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
            }
        }

        if (dp[n] == Integer.MAX_VALUE) {
            System.out.println(-1);
        }else{
            System.out.println(dp[n]);
        }
    }
}