백준 31804번 Chance! Java

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

문제

---

생각하기

---

• BFS 최적화 문제이다.

동작

처음에 memo배열을 1차원 배열로 관리했었는데, chance!사용 여부를 위해 memo 배열은 2차원 배열로 만들어야 한다.

그 이유는 낮은 값 단위에서 chance를 사용하는 것 보다 큰 값에서 chance를 사용하는게 더 유리하기 때문인데,

예를 들어 40까지 가는데 4에서 출발했을 때, 10을 사용하게 되어 memo[40]의 값은 1이 된다.

근데 M의 값이 2000쯤 된다고 했을 때, 200에서 10배를 하게 되면 곧바로 2000을 갈 수 있게 된다.

또한, 4에서 2배와 +1을 해서 40에 도달했을 때, 이미memo[40] = 1 이 최소값이므로 더 나아갈 수 없어서

2000까지 가는데, 최소값에 오류가 발생하게 된다.

예시는 그냥 예시일 뿐입니다. 2000까지 틀리게 나온다는 건 아닙니다.

결과

코드

---

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;

    private static class Magic {
        int score;
        int count;
        boolean chance;

        private Magic(int score, int count, boolean chance) {
            this.score = score;
            this.count = count;
            this.chance = chance;
        }
    } // End of Magic 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();

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

    private static int BFS() {
        ArrayDeque<Magic> que = new ArrayDeque<>();
        boolean[][] memo = new boolean[M + 1][2];
        que.offer(new Magic(N, 0, false));

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

            if (cur.score == M) {
                return cur.count;
            }
            if (memo[cur.score][cur.chance ? 1 : 0]) continue;
            memo[cur.score][cur.chance ? 1 : 0] = true;


            if (cur.score + 1 <= M) {
                que.offer(new Magic(cur.score + 1, cur.count + 1, cur.chance));
            }

            if (cur.score * 2 <= M) {
                que.offer(new Magic(cur.score * 2, cur.count + 1, cur.chance));
            }

            if (cur.score * 10 <= M && !cur.chance) {
                que.offer(new Magic(cur.score * 10, cur.count + 1, true));
            }
        }

        return -1;
    } // End of BFS()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
    } // End of input()
} // End of Main class