백준[11060] - 점프 점프

• 문제: https://www.acmicpc.net/problem/11060
• 분류: DP
• 난이도: S2
• 소요시간: 15m
• 자아성찰:
  • 브루트포스 느낌이 나는 DP 문제인 것 같다.
  • 이전 계산 기록을 기반으로 불필요한 연산을 하지 않도록 하는 매커니즘은 DP가 맞고,
  • 각 미로에 대해 이동할 수 있는 만큼 최소 점프 횟수를 하나하나 체크하는 매커니즘은 브루트포스 느낌이다.
  • 시간복잡도는 각 미로(N <= 1000)에 대해 이동 가능횟수 (A_i <= 100)를 모두 체크한다고 해도 O(NA_i) = 10만으로 DP를 통해 넉넉히 풀 수 있다.
  • 스스로 DP 문제를 보면 "아 이건 DP다!" 하고 바로 떠올리기 힘들기 때문에 다음과 같은 순서로 DP 풀이방식을 떠올리는 게 좋은 것 같다.
    • 브루트포스로 먼저 풀어본다.
    • 시간복잡도를 생각해보고, 오래걸린다 싶으면 브루트포스 로직에서 DP로 메모이제이션 할 수 있는 방법을 고안한다.
  • 이 문제는 브루트포스 + DP 느낌이라 위와 같은 과정을 연습하기 좋았던 것 같다.
  • 욕심 내지 말고, 쉬운 문제부터 다시 기초 쌓고 감을 잡자.

11060번: 점프 점프

---

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

public class B_11060 {

    static int[] DP, map;
    static int N;
    static final int MAX = 1_000_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        DP = new int[N];
        map = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 방문하지 않은 미로 최댓값 초기화
        for (int i = 0; i < N; i++) {
            map[i] = Integer.parseInt(st.nextToken());
            DP[i] = MAX;
        }
        // 처음 위치는 0으로 초기화
        DP[0] = 0;
        for (int i = 0; i < N; i++) {
            // 현재 위치의 값이 MAX일 경우 이동 불가능 한 위치이므로 continue
            if (DP[i] == MAX) continue;
            int num = map[i];
            // 현재 위치에서 이동 가능한 미로 순회하며 최소 이동횟수 업데이트
            for (int j = i + 1; j <= i + num; j++) {
                // map을 넘어갈 시 break
                if (j >= N) break;
                // 이동 가능한 미로의 최소 이동횟수 업데이트
                DP[j] = Math.min(DP[j], DP[i] + 1);
            }
        }
        System.out.println(DP[N - 1] == MAX ? -1 : DP[N - 1]);
    }
}