백준 11060번
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.LinkedList;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static final int INF = Integer.MAX_VALUE;
    private static int N;
    private static int[] arr;

    private static class Jump {
        int start; // 출발지
        int go; // 점프할 곳
        int jumpCount;

        private Jump(int start, int go, int jumpCount) {
            this.start = start;
            this.go = go;
            this.jumpCount = jumpCount;
        }
    } // End of Jump class

    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();
        if (ret == INF) {
            sb.append(-1);
        } else {
            sb.append(ret);
        }

        return sb.toString();
    } // End of solve()

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

        for (int i = 1; i <= arr[0]; i++) {
            memo[i] = 1;
            que.offer(new Jump(i, arr[i], memo[i]));
        }

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

            for (int i = 1; i <= current.go; i++) {
                if (current.start + i <= N - 1) {
                    if (memo[current.start + i] > memo[current.start] + 1) {
                        memo[current.start + i] = memo[current.start] + 1;
                        que.offer(new Jump(current.start + i, arr[current.start + i], memo[current.start + i]));
                    }
                }
            }
        }

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

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

        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 final int INF = Integer.MAX_VALUE;
    private static int N;
    private static int[] arr, memo;

    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();

        memo[0] = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 1; j <= arr[i]; j++) {
                if (memo[i] == INF) continue; // 이거 없이 Integer.MAX_VALUE INF 값으로 하면 overflow나서 오답됨 

                if (i + j <= N - 1) {
                    memo[i + j] = Math.min(memo[i] + 1, memo[i + j]);
                }
            }
        }

        if (memo[N - 1] == INF) {
            sb.append(-1);
        } else {
            sb.append(memo[N - 1]);
        }

        return sb.toString();
    } // End of solve()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        memo = new int[N];
        Arrays.fill(memo, INF);

        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