문제

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

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

입력

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

출력

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

import java.util.*;
import java.io.*;

public class Main {
    static int N;
    static int[] arr;
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        arr = new int[N+1];

        Queue<Integer> q = new LinkedList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            int n = Integer.parseInt(st.nextToken());
            arr[i] = n;
            q.add(n);
        }
        int cnt = 0;
        int index = 1;
        boolean ck = false;
        while (index < N) {
            int max = 0;
            int maxIndex = 0;
            for (int i = index+1; i <= arr[index]+index; i++) {
                if (max < arr[i]+i) {
                    max = arr[i]+i; // i를 더한 이유: 해당 인덱스로 최대 거리 측정.
                    maxIndex = i;
                }
                if (i >= N) {
                    ck = true;
                    break;
                }
            }
            if (arr[index] == 0) {
                cnt = -1;
                break;
            }
            index = maxIndex;
            cnt++;
            if (ck) break;
        }
        System.out.println(cnt);


    }

}

• index가 N보다 커지기 전에 해당 인덱스마다 경우의 수(index ~ arr[index]+index사이에서 arr[i]+i가 가장 큰 경우)가 가장 큰 인덱스를 선택해서 다음 인덱스로 할당.
• while문이 실행되는동안 i >= N이라면 중간에 끊어주기.