백준 11060번 : 점프 점프(Java)

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

11060번: 점프 점프

---

[풀이]

 

 이전 값을 저장할 dp 배열과 입력 값을 저장할 arr 배열을 만들었다. 다음 위치로 점프할 수 있는 거리는 0~arr[i]이다. 그러므로, for 반복문을 돌면서 최소값을 dp 배열에 저장하면 된다.

 

(주의해야할 부분)

 다음 위치로 점프할 수 있는 거리는 최소 0부터 arr[i] 까지이다. 그러므로 이 부분에 해당하는 인덱스를 주의해서 풀어야 한다.

 

---

[코드]

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        int[] arr = new int[N];
        int[] dp = new int[N];
        Arrays.fill(dp, -1);
        String line = bf.readLine();
        StringTokenizer st = new StringTokenizer(line, " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        dp[0] = 0;

        for (int i = 0; i < N - 1; i++) {
            if (dp[i] == -1) {
                continue;
            }
            for (int j = 1; j <= arr[i]; j++) {
                if (i + j < N) {
                    if (dp[i + j] == -1 || dp[i + j] > dp[i] + 1) {
                        dp[i + j] = dp[i] + 1;
                    }
                }
            }
        }
        System.out.println(dp[N - 1]);
    }
}