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

BOJ 12869 뮤탈리스크

난이도 : 골드 4

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

12869번: 뮤탈리스크

 

전략

처음에는 hp가 많이 남은 순으로 9, 3, 1을 배정해서 그리디로 풀 수 있을까 고민했다.

 

하지만 12, 9, 3 같은 경우를 생각해보면

12, 9, 3 -> 3, 6, 2 -> 0, 0, 1 -> 0, 0, 0 으로 3번이 되는데 최적의 방법은

12, 9, 3 -> 9, 0, 2 -> 0, 0, 0 으로 2번만에 가능한 것을 볼수 있다.

 

즉 경우의 수를 탐색해봐야 하므로 dp로 전략을 세워야한다.

scv는 1 ~ 3개이지만 dp 배열은 항상 3개로 고정시키고 scv가 3개 미만일 경우에는 처음부터 hp를 0으로 설정하면 된다.

 

-9, -3, -1을 배치하는 3! = 6개의 경우의 수를 dfs로 탐색하면서 메모이제이션을 활용해 중복된 연산을 제거할 수 있다.

 

나는 추가로 3개의 hp의 위치가 바뀌어도 같은 결과를 의미하기 때문에 더 높은 효율을 끌어낼 수 있도록 dp를 더 활용해보았다.

 

시행착오

사실 이 문제 풀면서 분명 맞는데 왜 자꾸 틀리지.. 했는데 한 군데에 오타가 있었다.. (hp 로컬 변수 이름에서)

 

한 번 크게 혼났으니까 다음부턴 더 신경쓰면서 할 것 같다.

 

코드

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

public class Main {

    static int[][][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] hp = new int[3];
        String[] line = br.readLine().split(" ");
        for (int i = 0; i < N; i++)
            hp[i] = Integer.parseInt(line[i]);

        dp = new int[61][61][61];
        for (int i = 0; i < dp.length; i++)
            for (int j = 0; j < dp[i].length; j++)
                for (int k = 0; k < dp[j].length; k++)
                    dp[i][j][k] = Integer.MAX_VALUE;
        dp[0][0][0] = 0;

        System.out.println(solution(hp[0], hp[1], hp[2]));
    }

    static int solution(int hp1, int hp2, int hp3) {
        hp1 = Math.max(hp1, 0);
        hp2 = Math.max(hp2, 0);
        hp3 = Math.max(hp3, 0);

        if (dp[hp1][hp2][hp3] != Integer.MAX_VALUE)
            return dp[hp1][hp2][hp3];
        if (dp[hp1][hp3][hp2] != Integer.MAX_VALUE)
            return dp[hp1][hp2][hp3] = dp[hp1][hp3][hp2];
        if (dp[hp2][hp1][hp3] != Integer.MAX_VALUE)
            return dp[hp1][hp2][hp3] = dp[hp2][hp1][hp3];
        if (dp[hp2][hp3][hp1] != Integer.MAX_VALUE)
            return dp[hp1][hp2][hp3] = dp[hp2][hp3][hp1];
        if (dp[hp3][hp1][hp2] != Integer.MAX_VALUE)
            return dp[hp1][hp2][hp3] = dp[hp3][hp1][hp2];
        if (dp[hp3][hp2][hp1] != Integer.MAX_VALUE)
            return dp[hp1][hp2][hp3] = dp[hp3][hp2][hp1];

        dp[hp1][hp2][hp3] = Math.min(dp[hp1][hp2][hp3], solution(hp1 - 9, hp2 - 3, hp3 - 1) + 1);
        dp[hp1][hp2][hp3] = Math.min(dp[hp1][hp2][hp3], solution(hp1 - 9, hp2 - 1, hp3 - 3) + 1);
        dp[hp1][hp2][hp3] = Math.min(dp[hp1][hp2][hp3], solution(hp1 - 3, hp2 - 9, hp3 - 1) + 1);
        dp[hp1][hp2][hp3] = Math.min(dp[hp1][hp2][hp3], solution(hp1 - 3, hp2 - 1, hp3 - 9) + 1);
        dp[hp1][hp2][hp3] = Math.min(dp[hp1][hp2][hp3], solution(hp1 - 1, hp2 - 9, hp3 - 3) + 1);
        dp[hp1][hp2][hp3] = Math.min(dp[hp1][hp2][hp3], solution(hp1 - 1, hp2 - 3, hp3 - 9) + 1);

        return dp[hp1][hp2][hp3];
    }
}

 

깨달은 점

간단한 dp문제라서 자신감을 얻기 좋은 것 같다.