백준 11060번 점프 점프 Java

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

문제

---

생각하기

---

• BFS, 가지치기, DP 문제이다.

동작

도움되는 반례

1
0

ans : 0


3
2 5 0

ans : 1


5
2 1 1 0 2

ans : -1


2
0 0

ans : -1


4
1 0 1 1

ans : -1

27% 에서 발생하는 에러 -> 오버플로우 확인해보자

DP 구현에서 계속 오답되서 원인을 찾아보니까 오버플로우가 나서 발생하는 에러였다.
i를 모두 순회하는 구조이다 보니 INF로 되어있는 memo[i] 값이 다른 값들과 더해지면 오버플로우가 날 수 밖에 없음

그래서 memo[i] == INF 로 아직 방문되지 않은 곳은 점프를 하는 조건이 있을 수가 없기 때문에 그냥 continue 처리했다.

생각보다 어렵지 않은 문제

결과

코드

---

BFS

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N;
    private static int[] arr;
    private static final int INF = Integer.MAX_VALUE / 2; // 오버플로우 방지

    private static class Jump implements Comparable<Jump> {
        int num;
        int count;

        private Jump(int num, int count) {
            this.num = num;
            this.count = count;
        }

        @Override
        public int compareTo(Jump o) {
            return count - o.count;
        }
    } // End of Jump()

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        int ret = BFS();

        sb.append(ret == INF ? -1 : ret);
        return sb.toString();
    } // End of solve()

    private static int BFS() {
        PriorityQueue<Jump> que = new PriorityQueue<>();
        int[] memo = new int[N + 1];
        Arrays.fill(memo, INF);
        memo[0] = 0;
        que.offer(new Jump(0, 0));

        while (!que.isEmpty()) {
            Jump cur = que.poll();

            if (cur.num == N - 1) {
                memo[cur.num] = Math.min(memo[cur.num], cur.count);
            }

            for (int i = cur.num + 1; i <= cur.num + arr[cur.num] && i < N; i++) {
                if (memo[i] > memo[cur.num] + 1) {
                    memo[i] = memo[cur.num] + 1;
                    que.offer(new Jump(i, memo[i]));
                }
            }
        }

        return memo[N - 1];
    } // End of BFS()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        arr = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
    } // End of input()
} // End of Main class

DP

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N;
    private static int[] arr;
    private static final int INF = Integer.MAX_VALUE / 2; // 오버플로우 방지

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        int ret = bottomUp();
        
        sb.append(ret == INF ? -1 : ret);
        return sb.toString();
    } // End of solve()

    private static int bottomUp() {
        int[] memo = new int[N + 1];
        Arrays.fill(memo, INF);

        memo[0] = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 1; j <= arr[i]; j++) {
                if (i + j >= N - 1) {
                    memo[N - 1] = Math.min(memo[i] + 1, memo[N - 1]);
                    continue;
                }

                memo[i + j] = Math.min(memo[i] + 1, memo[i + j]);
            }
        }

        return memo[N - 1];
    } // End of bottomUp()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        arr = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
    } // End of input()
} // End of Main class