백준 12869 (뮤탈리스크)

문제

12869번: 뮤탈리스크

SCV가 최대 n명 주어진다.

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

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

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

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

---

처음에 문제를 보자마자 dp라고 생각했다.

하지만 오랜만에 dp 문제를 푸니 점화식을 구할 수 없었다.

해당 문제의 dp 점화식을 구하는 핵심은 "공격횟수의 최솟값" 이다.

즉, dp 배열을 만들어 공격횟수의 최솟값을 넣는것이다.

예를 들어 dp[] = 최솟값 이런식으로..

 

그렇다면 직관적으로 dp[9][3][1] = 1 이런식으로 점화식을 세울 수 있을 것 같다.

(SCV 체력이 각각 9, 3, 1 남으면 1번만 공격해서 모두 0으로 만들 수 있다.)

 

이번에는 top-down 형식으로 작성했다.

private static int sol(int a, int b, int c){
        a = Math.max(a, 0); //음수가 나올 경우 0으로 보정
        b = Math.max(b, 0);
        c = Math.max(c, 0);

        if(a+b+c == 0)return 0; //a, b, c가 모두 0일 경우 0을 return, 이 때 부터 공격횟수 +1 증가하기 시작함
        if(dp[a][b][c] != 0)return dp[a][b][c]; //이미 이전에 계산되었을 경우(메모이제이션)

        int ret = Integer.MAX_VALUE;
        ret = Math.min(ret, sol(a-9, b-3, c-1) +1);
        ret = Math.min(ret, sol(a-9, b-1, c-3) +1);
        ret = Math.min(ret, sol(a-3, b-9, c-1) +1);
        ret = Math.min(ret, sol(a-1, b-9, c-3) +1);
        ret = Math.min(ret, sol(a-3, b-1, c-9) +1);
        ret = Math.min(ret, sol(a-1, b-3, c-9) +1);

        dp[a][b][c] = ret;
        return ret;

    }

주석을 잘 읽으면 이해가된다.

---

전체 코드이다.

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

        int n = Integer.parseInt(st.nextToken());
        int []scv = new int[3];
        Arrays.fill(scv, 0);

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

        dp = new int[61][61][61];

        System.out.println(sol(scv[0], scv[1], scv[2]));


    }
    private static int sol(int a, int b, int c){
        a = Math.max(a, 0);
        b = Math.max(b, 0);
        c = Math.max(c, 0);

        if(a+b+c == 0)return 0;
        if(dp[a][b][c] != 0)return dp[a][b][c];

        int ret = Integer.MAX_VALUE;
        ret = Math.min(ret, sol(a-9, b-3, c-1) +1);
        ret = Math.min(ret, sol(a-9, b-1, c-3) +1);
        ret = Math.min(ret, sol(a-3, b-9, c-1) +1);
        ret = Math.min(ret, sol(a-1, b-9, c-3) +1);
        ret = Math.min(ret, sol(a-3, b-1, c-9) +1);
        ret = Math.min(ret, sol(a-1, b-3, c-9) +1);

        dp[a][b][c] = ret;
        return ret;

    }

}