[백준/Java] 11060번 : 점프 점프

✏️ 문제 분석

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

 

N개의 일렬로 놓여진 칸 위에서 점프를 한다.

가장 왼쪽 끝에서 가장 오른쪽 끝으로 가려면 최소 몇 번 점프해야 갈 수 있는가?

한 번에 점프 가능한 횟수는 현재 있는 칸에 적힌 수이다.

✏️ 구현 아이디어

현재 칸에 다다르기 위한 최소 점프 횟수 + 1을 현재 칸에서 이동할 수 있는 모든 곳에 저장하는 것을 반복한다.

단, 최소값만 저장한다.

✏️ 알고리즘

dp 동적 계획법

✏️ 시간 복잡도

모든 칸을 한 번만 방문하므로 탐색의 시간 복잡도는 O(N)

탐색할 때마다 비교하는 연산은 O(1)

N은 최대 1,000이므로 시간 안에 연산 가능하다.

✏️ 코드 설계

1. arr에 입력값을 받는다.
2. 최소 몇 번의 점프만에 도달할 수 있는지 저장할 dp배열을 모두 Integer.MAX_VALUE로 초기화한다.
3. dp[0]은 시작하는 곳이므로 값을 0으로 초기화한다.
4. 최소 점프 횟수를 갱신한다.
5. 도달 가능하면 dp[n-1]을, 불가능하면 -1을 출력한다.

✏️ 정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE); // 초기값을 MAX_VALUE로 설정

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

        dp[0] = 0; // 시작 위치의 점프 횟수는 0

        for (int i = 0; i < n; i++) {
            if (dp[i] == Integer.MAX_VALUE) continue; // 도달 불가능한 위치는 건너뜀

            // 현재 위치에서 점프 가능한 범위 갱신
            for (int j = 1; j <= arr[i]; j++) {
                if (i + j >= n) break; // 배열 범위 초과 시 종료
                dp[i + j] = Math.min(dp[i + j], dp[i] + 1); // 최소 점프 횟수 갱신
            }
        }

        // 마지막 위치에 도달할 수 있는지 확인 후 출력
        System.out.println(dp[n - 1] == Integer.MAX_VALUE ? -1 : dp[n - 1]);
    }
}