[BOJ] 12869 : 뮤탈리스크(Java)

문제

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

---

💡 풀이

DFS에서 DP의 개념을 살짝 더하여 풀이했다. 풀이 과정은 다음과 같다.

1. 입력값 s1, s2, s3(현재 scv의 체력)에 대해 재귀를 이용하여 {-9, -3, -1}, {-9, -1, -3}, {-3, -9, -1}, {-3, -1, -9}, {-1, -3, -9}, {-1, -9, -3}를 수행한다. 
2. 이때 중복을 줄이기 위해 visited 배열을 이용한다. vistied[a][b][c]는 체력이 a,b,c인 scv들을 계산한 적이 있는 경우 바로 함수를 종료하게 된다. 만약 방문하지 않았다면 방문체크(true)를 한 뒤 3번 연산을 수행한다. 
3. 1번에서 1씩 증가되며 함께 넘어오는 count 인자가 계산된 scv가 모두 죽어서 반환된 result 값보다 크다면, 계산할 필요가 없기 때문에 함수를 종료한다. 
4. 위 2, 3번의 상황이 아니라면 count를 1증가 시키며 1번의 과정으로 넘어간다.

여기서 주의할 점은 s1 = 8, s2 = 4, s3 = 6인 경우와 s1 = 6, s2 = 4, s3 = 8인 경우는 같은 상황이다. 따라서 visited에서 방문 여부를 확인할 때 visited[a][b][c]에 대해 a,b,c 순서로 큰 수대로 넣어주는 방법을 사용했다. 

 

전체적인 코드는 다음과 같다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Q12869 {
    public static int[] scv;
    // 중복을 피하기 위해 이미 처리한 값에 대한 처리
    public static boolean[][][] visited = new boolean[61][61][61];
    public static int result=(int)1e9;

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

        int N = Integer.parseInt(br.readLine()); // SCV 수
        st = new StringTokenizer(br.readLine());

        scv = new int[3];
        for (int i = 0; i < N; i++) {
            scv[i] = Integer.parseInt(st.nextToken());
        }
        // scv 개수가 3보다 작으면 나머지는 0으로 채워주기
        for (int i = N; i < 3; i++) {
            scv[i] = 0;
        }
        int s1=scv[0], s2=scv[1], s3=scv[2];

        findMin(s1, s2, s3, 0);
        System.out.println(result);

    }

    public static void findMin(int a, int b, int c, int count) {
        // 음수라면 0으로 만들기
        a = Math.max(0, a);
        b = Math.max(0, b);
        c = Math.max(0, c);

        // 모든 scv가 죽었을 경우
        if(a==0 & b==0 && c==0){
            result = Math.min(result, count);
            return;
        }

        // a,b,c 순서로 큰 수대로 입력
        int[] sorting = {a,b,c};
        Arrays.sort(sorting);
        c = sorting[0];
        b = sorting[1];
        a = sorting[2];

        // 이미 계산한 값에 대한 중복을 피하기 위해 방문 했다면 종료
        if(visited[a][b][c])
            return;
        else
            visited[a][b][c]=true;

        // 현재 계산 중인 count가 result보다 크다면 더 계산할 필요없이 바로 종료
        if(result<count)
            return;

        findMin(a-9, b-3, c-1, count+1);
        findMin(a-9, b-1, c-3, count+1);
        findMin(a-3, b-9, c-1, count+1);
        findMin(a-3, b-1, c-9, count+1);
        findMin(a-1, b-3, c-9, count+1);
        findMin(a-1, b-9, c-3, count+1);

        return;
    }
}