[BOJ G4][#DP/BFS]12869번 뮤탈리스크

뮤탈리스크 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

10339

4958

3485

47.006%

문제

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.

각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.

뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.

1. 첫 번째로 공격받는 SCV는 체력 9를 잃는다.
2. 두 번째로 공격받는 SCV는 체력 3을 잃는다.
3. 세 번째로 공격받는 SCV는 체력 1을 잃는다.

SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.

남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 SCV의 수 N (1 ≤ N ≤ 3)이 주어진다. 둘째 줄에는 SCV N개의 체력이 주어진다. 체력은 60보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 SCV를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

예제 입력 1 복사

3
12 10 4

예제 출력 1 복사

2

예제 입력 2 복사

3
54 18 6

예제 출력 2 복사

6

예제 입력 3 복사

1
60

예제 출력 3 복사

7

예제 입력 4 복사

3
1 1 1

예제 출력 4 복사

1

예제 입력 5 복사

2
60 40

예제 출력 5 복사

9

힌트

1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다

 

 

 

📝 풀이

처음 생각한 것은 BFS로 푸는 것이였다.

 

필살 깡으로 풀어보기

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int num[];
    static int N;
    static int result = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        num = new int[3];
        for(int i = 0; i < N; i++){
            num[i] = Integer.parseInt(st.nextToken());
        }
        bfs();
        System.out.println(result);

    }
    public static void bfs(){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{num[0], num[1], num[2], 0});

        while(!q.isEmpty()){
            int arr[] = q.poll();
            int num1 = arr[0];
            int num2 = arr[1];
            int num3 = arr[2];
            int count = arr[3];
            if(isVaild(num1, num2, num3)){
                result = Math.min(count, result);
                return;
            }
            q.add(new int[]{num1-9, num2-3, num3-1, count + 1});
            q.add(new int[]{num1-3, num2-9, num3-1, count + 1});
            q.add(new int[]{num1-3, num2-1, num3-9, count + 1});
            q.add(new int[]{num1-9, num2-1, num3-3, count + 1});
            q.add(new int[]{num1-1, num2-3, num3-9, count + 1});
            q.add(new int[]{num1-1, num2-9, num3-3, count + 1});
        }
    }
    public static boolean isVaild(int a, int b, int c){
        return a <= 0 && b <= 0 && c <= 0;
    }
}

 

역시는 역시...

 

 

메모리 초과가 일어나는 문제를 생각해보면 큐에 너무 많은 것을 넣은 것 같았다.

여러 가능성 중에서 한번 들린 방향은 다시 안하게 하는 제한이 필요하다 생각하였다.

 

그래서 BFS에서 DP를 갱신하는 방식으로 풀어보았다.

 

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

public class Main {
    static int[] num;
    static int N;
    static int[][][] dp;
    static final int[][] ATTACKS = {
        {9, 3, 1},
        {9, 1, 3},
        {3, 9, 1},
        {3, 1, 9},
        {1, 9, 3},
        {1, 3, 9}
    };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        num = new int[3];
        for (int i = 0; i < N; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }
        
        // DP 배열을 60으로 초기화 (최대 체력 60)
        dp = new int[61][61][61];
        for (int[][] matrix : dp) {
            for (int[] row : matrix) {
                Arrays.fill(row, Integer.MAX_VALUE);
            }
        }

        bfs();
        // dp[0][0][0]에 저장된 최소 공격 횟수 출력
        System.out.println(dp[0][0][0]);
    }

    public static void bfs() {
        Queue<int[]> queue = new LinkedList<>();
        // 초기 상태와 공격 횟수 0
        queue.add(new int[]{num[0], num[1], num[2]});
        dp[num[0]][num[1]][num[2]] = 0;

        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int num1 = arr[0];
            int num2 = arr[1];
            int num3 = arr[2];
            int currentCount = dp[num1][num2][num3];
            
            // 가능한 모든 공격 패턴 적용
            for (int[] attack : ATTACKS) {
                int move1 = Math.max(num1 - attack[0], 0);
                int move2 = Math.max(num2 - attack[1], 0);
                int move3 = Math.max(num3 - attack[2], 0);
                //최소인 것만 큐에 검사
                if (dp[move1][move2][move3] > currentCount + 1) {
                    dp[move1][move2][move3] = currentCount + 1;
                    queue.add(new int[]{move1, move2, move3});
                }
            }
        }
    }
}