[백준]:12869: 뮤탈리스크(java)

 

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

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를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

예제 입력 1 복사

3
12 10 4

예제 출력 1 복사

2

---

풀이

1. 단계적 데미지가 들어간다. > 저는 단계적인 무언가를 하면 BFS를 사용합니다.

2. 9, 3, 1은 총 3!인 6가지 경우의 수로 데미지를 입힐 수 있다.

3. BFS로 bottom-top방식을 이용해 누적하여 딜을 적용시켜본 후 depth를 찾아준다.

- 이때 visited는 3차원 배열로 각 scv의 hp를 중복해서 만들지 못하게 해줌으로써 시간초과를 피해갈 수 있다.

 

 

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static class SCV{
        int s1;
        int s2;
        int s3;
        int cnt;
        SCV(int s1, int s2, int s3, int cnt) {
            this.s1 = s1;
            this.s2 = s2;
            this.s3 = s3;
            this.cnt = cnt;
        }

    }

    public static void main(String[] args) throws IOException {
        int[] scv = new int[3];
        int N;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            scv[i] = Integer.parseInt(st.nextToken());
        }
        bfs(scv);
    }

    private static void bfs(int[] scv) {
        boolean [][][] visited = new boolean[61][61][61];
        int[][] deal = {{9, 3, 1}, {9, 1, 3}, {3, 9, 1}, {3, 1, 9}, {1, 3, 9}, {1, 9, 3}};
        int[][][] dp = new int[61][61][61];
        Queue<SCV> q = new LinkedList<>();

        visited[0][0][0] = true;
        q.add(new SCV(0, 0, 0, 0));

        while(!q.isEmpty()) {
            SCV now = q.poll();

            for(int i=0; i<6; i++) {
                int nextS1 = now.s1+deal[i][0];
                int nextS2 = now.s2+deal[i][1];
                int nextS3 = now.s3+deal[i][2];
                if(nextS1 > 60) nextS1 = 60;
                if(nextS2 > 60) nextS2 = 60;
                if(nextS3 > 60) nextS3 = 60;

                if(visited[nextS1][nextS2][nextS3]) continue;
                if(nextS1 >= scv[0] && nextS2 >= scv[1] && nextS3 >= scv[2]) {
                    System.out.println(now.cnt+1);
                    return;
                }
                visited[nextS1][nextS2][nextS3] = true;
                q.add(new SCV(nextS1, nextS2, nextS3, now.cnt+1));
            }
        }

    }
}