백준 2253번 : 점프 [자바]

 

 

🧫 문제 분석

 

✔️ 출처

점프 골드 4

 

📖 문제

 

dp 문제

갈 수 없는 돌들이 있으므로 여러가지 경우의 수가 있기에 가장 먼저 출발한 것이 먼저 도착하는 것이 아니다.

각 돌에 도착할때 몇 점프로 도달했는지를 체크해줄 필요가 있다.

 

따라서 2차원 DP로 풀어야하는데 N*N 은 너무 커서 문제 조건에 맞지 않는다.

 

점프를 해도 결국 연속으로 누적된 x + 1이 가장 클 것이므로 

연속으로 x + 1 이 누적되었을때 1만까지의 값은 142 정도이다.

넉넉하게 150으로 잡았다. 

 

따라서 2차원 DP는 몇칸으로 현재 번호의 돌에 도착했는지 체크하면서 몇 번 점프했는지 값을 찾는다.

dp[현재 돌][몇 칸 점프해서 왔는지 점프 길이 : x] 

 

탐색에는 BFS 탐색을 사용한다. 

x-1, x, x+1 칸으로 점프하는 각각의 경우를 BFS로 탐색해주면된다.  

 

 

그리고 생각을 잘못한게 

입력 조건에서 1번과 N번은 충분히 크기가 크다고 했는데

이걸 제대로 안봐서 2번이 갈 수 없는 경우를 생각하지 못해서

96퍼에서 틀렸다. 

 

급하게 풀면 안된다. 문제를 꼼꼼히 여러번 읽자

 

---

🔅 문제 풀이

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

public class Main {
    static int N, M;
    static int[][] dp;
    static boolean[] smallRock;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        dp = new int[N + 1][150];
        smallRock = new boolean[N + 1];

        for (int i = 0; i < M; i++) {
            int idx = Integer.parseInt(br.readLine());
            smallRock[idx] = true;
        }

        if (smallRock[2]) {
            System.out.println(-1);
            return;
        }

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

        int answer = Integer.MAX_VALUE;

        for (int i = 0; i < dp[N].length; i++) {
            if (dp[N][i] == -1) continue;

            answer = Math.min(answer, dp[N][i]);
        }

        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);

    }

    private static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {2, 1}); // 현재 돌 번호, 점프해온 거리 x
        dp[2][1] = 1;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int curN = cur[0];
            int x = cur[1];

            if (curN == N) {
                return;
            }

            int nextRock = curN + (x - 1);
            if (x - 1 > 0 && nextRock <= N) {
                if (dp[nextRock][x-1] == -1 && !smallRock[nextRock]) {
                    dp[nextRock][x-1] = dp[curN][x] + 1;

                    q.add(new int[]{nextRock, x - 1});
                }
            }

            nextRock = curN + x;
            if (nextRock <= N) {
                if (dp[nextRock][x] == -1 && !smallRock[nextRock]) {
                    dp[nextRock][x] = dp[curN][x] + 1;
                    q.add(new int[]{nextRock, x});
                }
            }

            nextRock = curN + x + 1;
            if (nextRock <= N) {
                if (dp[nextRock][x+1] == -1 && !smallRock[nextRock]) {
                    dp[nextRock][x+1] = dp[curN][x] + 1;
                    q.add(new int[]{nextRock, x + 1});
                }
            }
        }
    }

}

 

 

 

❗ 오답노트 / 필요한 지식

1.  문제 잘 읽기
2. 급하게 풀지 말