[백준] 12869번 - 뮤탈리스크 (Gold 4)

문제 링크

백준 12869번 - 뮤탈리스크 (Gold 4)

문제 설명

$N(\leq 3)$개의 SCV를 최소한의 공격횟수로 없애려고 한다.
한번에 3개의 SCV를 공격할 수 있는데, 첫 번쨰로 공격받는 SCV는 체력 9를, 두 번째로 공격받는 SCV는 체력 3을, 세 번째로 공격받는 SCV는 체력 1을 잃는다.
SCV의 체력이 0 이하가 되면 파괴된다고 할 때, 모든 SCV를 파괴하기 위한 최소 공격 횟수를 구하시오.
단, 처음 SCV의 체력은 각 60을 넘지 않는다.

정답 코드 및 설명

DP를 이용하여 풀면 된다.
SCV의 체력이 a, b, c일 때 모든 SCV를 파괴하기 위한 최소 공격 횟수를 $f(a, b, c)$라고 두자.
그러면 $f(a, b, c) = \textrm{min}\lbrace f(a-p, b-q, c-r) : \lbrace p, q, r\rbrace = \lbrace 1, 3, 9 \rbrace \rbrace + 1$이다.
또한, $a \leq 0, b \leq 0, c\leq 0$이면 $f(a, b, c) = 0$이다.

이 점화식을 코드로 구현하면 아래와 같다.
시간 복잡도를 정확히 구하기는 쉽지 않으나, $61^3$개 이하의 f(a, b, c)값을 계산하게 되고, 한번의 계산에는 대략 3! = 6번의 계산이 필요하므로 총 계산 횟수가 2억번은 절대 넘지 않는다.
따라서, 시간 제한 2초 안에 충분히 해결 가능하다. (실제로 아래 코드로 제출했을 때는 132ms가 나왔다.)

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

public class BOJ12869 {
    final int[] ATTACK = {1, 3, 9};
    final int[][] PERMUTATION = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};
    int[] scv;
    int[][][] minAttack = new int[61][61][61];

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        scv = new int[3];
        for (int i = 0; i < n; i++)
            scv[i] = Integer.parseInt(st.nextToken());
        for (int i = n; i < 3; i++)
            scv[i] = 0;
    }

    int dp(int[] scv) {
        if (scv[0] == 0 && scv[1] == 0 && scv[2] == 0)
            return 0;
        if (minAttack[scv[0]][scv[1]][scv[2]] != 0)
            return minAttack[scv[0]][scv[1]][scv[2]];
        int min = Integer.MAX_VALUE;
        for (int[] permutation : PERMUTATION) {
            int[] currSCV = new int[3];
            for (int i = 0; i < 3; i++) {
                currSCV[i] = Math.max(scv[i] - ATTACK[permutation[i]], 0);
            }
            int temp = dp(currSCV) + 1;
            if (min > temp)
                min = temp;
        }
        return minAttack[scv[0]][scv[1]][scv[2]] = min;
    }

    void solution() throws IOException {
        input();
        System.out.println(dp(scv));
    }

    public static void main(String[] args) throws IOException {
        new BOJ12869().solution();
    }
}