[BOJ/JAVA] 11060번: 점프 점프

11060번: 점프 점프

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

키워드

i번째 칸에 쓰여 있는 수를 $A_i$라고 했을 때, 재환이는 $A_i$이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다.

가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력

---

구현

private static int dp(int index, int count)

현재 위치가 index이고, 뛴 횟수가 count일 때 끝까지 갈 때의 최소 점프 횟수 반환하는 메소드

• 끝에 도달한 경우 (index == N-1)
  • 현재까지 뛴 횟수를 반환한다.

• 캐시값이 존재하는 경우 (cache[index][count] ≠ -2)
  • 캐시값을 반환한다.

• 갈 수 있는 경로를 탐색한다.
  • 범위는 [1, A[index]] 이다.
  • 만약 뛰는 거리가 배열 밖을 벗어나면 반복문을 종료한다.

---

코드

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

public class java_11060 {
    static int N;
    static int A[];

    static int cache[][];

    public static void main(String[] args) throws IOException {
        // A_i 이하 만큼 한번에 점프할 수 있다.

        // 최소 몇 번 점프를 해야하는지 구하기

        // 못구하면 -1

        // 너비우선 탐색

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 입력받기
        N = Integer.parseInt(br.readLine());

        A = new int[N];
        // A 입력받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        // A_0 위치에서 뛰어보기
        int result = solution();

        System.out.println(result);

        br.close();
    }

    // [i] 에서 오른쪽으로 최소 점프해서 갈 수 있는 값
    private static int solution() {
        cache = new int[N][N];

        for (int i = 0; i < N; i++) {
            Arrays.fill(cache[i], -2);
        }

        int result = dp(0, 0);

        if (result >= 987654321) {
            result = -1;
        }

        return result;
    }

    private static int dp(int index, int count) {
        // 끝에 도달한 경우
        if (index == N - 1) {
            return count;
        }

        if (cache[index][count] != -2) {
            return cache[index][count];
        }

        cache[index][count] = 987654321;

        // 갈 수 있는 경우 추가
        // 뛸 수 있는 칸 수 [1,A_i]
        // 배열의 범위를 벗어나는 경우도 체크
        for (int i = 1; i <= A[index] && index + i < N; i++) {
            cache[index][count] = Math.min(cache[index][count], dp(index + i, count + 1));
        }

        return cache[index][count];
    }
}

---

Uploaded by N2T