백준 27971번
https://www.acmicpc.net/problem/27971

문제

---

생각하기

---

• BFS 최적화 문제이다.

동작

BFS를 통해서 A마법과 B마법을 진행했을 때 갈래를 que로 잘 퍼트리면 된다.

            // A마법을 썼을 때,
            if (current.dogCount + A <= N && memo[current.dogCount + A] > memo[current.dogCount] + 1) {
                memo[current.dogCount + A] = memo[current.dogCount] + 1;
                que.offer(new Room(current.dogCount + A, memo[current.dogCount + A]));
            }

            if (current.dogCount + B <= N && memo[current.dogCount + B] > memo[current.dogCount] + 1) {
                memo[current.dogCount + B] = memo[current.dogCount] + 1;
                que.offer(new Room(current.dogCount + B, memo[current.dogCount + B]));
            }

그리고 닫힌 구간에 포함되는 강아지 숫자가 되었을 때는 0마리가 되므로 더 이상 진행하지 않는다.

    private static boolean isAbleCheck(int dogCount) {
        for (int i = 0; i < M; i++) {
            if (arr[i][0] <= dogCount && arr[i][1] >= dogCount) {
                return false;
            }
        }

        return true;
    } // End of isAbleCheck

...
            
    if (!isAbleCheck(current.dogCount)) continue; // 닫힌 구간에 들어갈 경우 다시 0마리로

결국 A, B 마법을 쓰면서 N마리에 가장 빨리 도달하여야 하므로 BFS를 사용하는거고
중복 방지를 위해 memoization을 사용한다.

조건만 잘 파악한다면 어렵지 않게 풀 수 있다.

결과

코드

---

import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
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, M, A, B;
    private static int[][] arr;

    private static class Room {
        int dogCount;
        int magicCount;

        private Room(int dogCount, int magicCount) {
            this.dogCount = dogCount;
            this.magicCount = magicCount;
        }
    } // End of Room 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() {
        Queue<Room> que = new ArrayDeque<>();
        int[] memo = new int[N + 1]; // index는 마리 수 // 값은 행동 횟수
        Arrays.fill(memo, INF);

        que.offer(new Room(0, 0));
        memo[0] = 0;

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

            if (memo[current.dogCount] < current.magicCount) continue;
            if (current.dogCount == N) {
                return current.magicCount;
            }

            if (!isAbleCheck(current.dogCount)) continue; // 닫힌 구간에 들어갈 경우 다시 0마리로

            // A마법을 썼을 때,
            if (current.dogCount + A <= N && memo[current.dogCount + A] > memo[current.dogCount] + 1) {
                memo[current.dogCount + A] = memo[current.dogCount] + 1;
                que.offer(new Room(current.dogCount + A, memo[current.dogCount + A]));
            }

            if (current.dogCount + B <= N && memo[current.dogCount + B] > memo[current.dogCount] + 1) {
                memo[current.dogCount + B] = memo[current.dogCount] + 1;
                que.offer(new Room(current.dogCount + B, memo[current.dogCount + B]));
            }
        }

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

    private static boolean isAbleCheck(int dogCount) {
        for (int i = 0; i < M; i++) {
            if (arr[i][0] <= dogCount && arr[i][1] >= dogCount) {
                return false;
            }
        }

        return true;
    } // End of isAbleCheck

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

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