[Algorithm] 백준_강아지는 많을수록 좋다_27971번 (JAVA) BFS, DP

📝문제

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

 

문제

마법소녀 마도카의 고양이에 깊은 감명을 받은 마법소녀 호무라는 자신도 마법을 이용하여 강아지 N$N$마리를 집에서 키우기로 결심했다!

호무라는 한 번의 행동에서 다음 2$2$가지 마법 중 하나를 선택하여 사용한다. 가장 처음에는 호무라의 집에 강아지가 존재하지 않는다.

•  A$A$-생성 마법: 강아지 A$A$마리를 호무라의 집에 생성한다.
•  B$B$-생성 마법: 강아지 B$B$마리를 호무라의 집에 생성한다.

그러나 미숙한 마법 사용은 호무라에게 추가적인 제약 사항을 주게 되었다. 만약 호무라의 방에 생성된 강아지의 수가 M$M$개의 닫힌구간들 [L1,R1],[L2,R2],⋯,[LM,RM]${[L_1,R_1],[L_2,R_2],\cdots,[L_M,R_M]}$ 중 하나 이상에 포함되게 된다면, 그 즉시 방에 생성된 모든 강아지가 사라지게 된다!

이를 명심하면서, 호무라는 위의 2$2$가지 마법을 적절히 사용하여, 최소의 행동 횟수로 호무라의 집에 정확히 N$N$마리의 강아지가 있도록 만들고 싶다. 계산을 어려워하는 호무라를 위해 최소의 행동 횟수를 계산해주자!

입력

첫 번째 줄에 키우기를 원하는 강아지의 수 N(2≤N≤100000)$N (2\leq N\leq 100\,000)$, 제약 사항에 해당하는 닫힌구간의 개수 M(1≤M≤100)$M (1\leq M\leq 100)$, 그리고 A$A$와 B(1≤A,B≤N)$B (1\leq A,B\leq N)$가 띄어쓰기로 구분되어 주어진다. 그 다음 M$M$줄에 걸쳐서, 각 줄에 제약 사항에 해당하는 닫힌구간의 양 끝점이 주어진다. 1≤i≤M$1\leq i\leq M$에 대하여 Li$L_i$와 Ri$R_i$는 1$1$ 이상 N−1$N-1$ 이하의 정수이며, Li≤Ri$L_i\leq R_i$이다.

출력

첫 번째 줄에 정확히 N$N$마리의 강아지를 호무라의 집에 들일 수 있는 최소의 행동 횟수를 출력한다. 만약 불가능하다면 −1$-1$을 출력한다.

---

💡풀이

문제 유형

너비우선탐색

DFS

 

걸린 시간

50분

 

티어

실버1

 

풀이 방법 도출

1. 현재 수에 A 또는 B를 더해 N을 만들어야 하므로 bfs를 풀이 방법으로 떠올렸다.
2. 구간의 수들은 Set을 사용하여 중복되지 않게 넣어주었고
3. set에 포함되지 않으면서 방문하지 않은 수들만 queue에 넣어주었다.
4. 이 문제는 다이나믹 프로그래밍으로도 해결할 수 있는데
5. dp[i]를 i마리일때 최소 횟수를 저장하는 배열로 설정하고 
6. dp[i+A] = Math.min(dp[i+A], dp[i]+1); 식을 세워 풀이를 이어갔다.
7. 이때 i+A는 구간 밖의 수이면서, N 이하의 수여야하고 dp[i]는 int의 최대값이 아닌 수여야한다.

BFS

import java.util.*;
import java.io.*;
class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        HashSet<Integer> set = new HashSet<>();

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            for(int j = a; j <= b; j++){
                set.add(j);
            }
        }

        boolean[] visited = new boolean[N+1];
        int answer = -1;
        Queue<int[]> queue = new LinkedList<>();
        if(!set.contains(A)){
            visited[A] = true;
            queue.add(new int[]{A,1});
        }
        if(!set.contains(B)){
            visited[B] = true;
            queue.add(new int[]{B,1});
        }

        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            
            if(cur[0] == N){
                answer = cur[1];
                break;
            }
            
            int nextTotalA = A+cur[0];
            if(nextTotalA <= N && !set.contains(nextTotalA) && !visited[nextTotalA]){
                visited[nextTotalA] = true;
                queue.add(new int[]{nextTotalA, cur[1]+1});
            }
            
            int nextTotalB = B+cur[0];
            if(nextTotalB <= N && !set.contains(nextTotalB) && !visited[nextTotalB]){
                visited[nextTotalB] = true;
                queue.add(new int[]{nextTotalB, cur[1]+1});
            }
        }

        System.out.println(answer);
    }
}

 

DP

import java.util.*;
import java.io.*;
class Main{
    static final int INF = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        HashSet<Integer> set = new HashSet<>();

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            for(int j = a; j <= b; j++){
                set.add(j);
            }
        }

        int[] dp = new int[N+1]; //x마리를 들일 때 최소 행동 횟수

        for (int i = 1; i <= N; i++) {
            dp[i] = INF;
        }

        for(int i = 0; i <= N; i++){
            if(!set.contains(i+A) && i+A <= N && dp[i] != INF){
                dp[i+A] = Math.min(dp[i+A], dp[i]+1);
            }
            if(!set.contains(i+B) && i+B <= N && dp[i] != INF){
                dp[i+B] = Math.min(dp[i+B], dp[i]+1);
            }
        }

        System.out.println(dp[N] == INF ? -1 : dp[N]);
    }
}