[백준 - 12869][GOLD 4][해설 X] - 뮤탈리스크 (JAVA)

문제 링크

---

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

 

문제

---

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 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를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        SCVGroup scvGroup = new SCVGroup();
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0;i<N;i++){
            int health = Integer.parseInt(st.nextToken());
            scvGroup.scv[i] = health;
        }

        int count = getMinCount(scvGroup);

        System.out.println(count);
    }
    
    //최소 횟수를 구하는 메소드
    public static int getMinCount(SCVGroup startGroup){
        PriorityQueue<SCVGroup> pq = new PriorityQueue<>((a,b)->(a.count - b.count));
        pq.add(startGroup);

        int minCount = Integer.MAX_VALUE;
        boolean[][][]visited = new boolean[61][61][61];

        while(!pq.isEmpty()){
            SCVGroup curr = pq.poll();

            visited[curr.scv[0]][curr.scv[1]][curr.scv[2]] = true;

            if(curr.scv[0] == 0 && curr.scv[1] == 0 && curr.scv[2] == 0){
                minCount = curr.count;
                break;
            }
            
            //조합으로 SCV 선정
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++){
                    if(i == j){
                        continue;
                    }
                    for(int k=0;k<3;k++){
                        if(i == k || j == k){
                            continue;
                        }

                        int[] nextSCV = new int[3];

                        nextSCV[i] =  curr.scv[i] - 9 < 0 ? 0 : curr.scv[i] - 9;
                        nextSCV[j] =  curr.scv[j] - 3 < 0 ? 0 : curr.scv[j] - 3;
                        nextSCV[k] =  curr.scv[k] - 1 < 0 ? 0 : curr.scv[k] - 1;

                        if(visited[nextSCV[0]][nextSCV[1]][nextSCV[2]]){
                            continue;
                        }

                        visited[nextSCV[0]][nextSCV[1]][nextSCV[2]] = true;

                        SCVGroup next = new SCVGroup(nextSCV,curr.count+1);
                        pq.add(next);
                    }
                }
            }
        }

        return minCount;
    }
}

class SCVGroup{
    int[] scv;
    int count;

    public SCVGroup(){
        scv = new int[3];
    }

    public SCVGroup(int[] scv, int count){
        this.scv = scv;
        this.count = count;
    }

}

 

 

실행 결과

---

 

 

팁

---

• 숫자가 작다면 모든 경우의 수를 생각해보자