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

문제 링크

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

12869번: 뮤탈리스크

풀이

전체적인 풀이 과정은 다음과 같다.

1. 체력을 저장할 배열(길이 3), 그리고 dp에 사용할 3중 배열 초기화
2. 이후 dp 기반 완전탐색 함수를 생성(인자 hp 3개)
   1) 현재 인자로 들어온 hp 3개가 모두 0이하라면, 0반환
   2) 해당 상황에 대한 계산 결과가 이미 존재한다면 해당 값 반환
   3) 3개의 hp에 대해 공격을 했을 때 발생할 수 있는 모든 경우의 수를 확인해, 최적의 값 확인
   4) 해당 값을 dp 배열에 저장하며 반환
3. 최초의 hp를 바탕으로 완전탐색을 진행하고, 그 결과를 출력

 당연히 현재 상황에서 최적의 상황이 어떻게 흘러갈 것인지 알 수 없다보니, 완전탐색 기반으로 접근해야 한다. 하지만 완전탐색의 경우 시간초과의 가능성이 매우 높기 때문에 각각의 hp 값을 인덱스 삼아, dp를 활용하면 시간을 줄일 수 있다.
 우선 각각의 hp를 저장할 배열, 그리고 dp에 활용할 3중 배열을 초기화한다. 그 다음엔 바로 완전탐색을 진행할 함수를 구현하는데, 우선 인자로는 각각의 hp 3개를 받는다. 우선 기저조건은 각각의 hp가 모두 0이하라면 0을 반환하는 조건이다. 이후 dp를 위해 해당 계산 결과가 이미 존재한다면, 해당 값을 반환한다. 그 다음에는 단순하게, 3개의 SCV를 공격할 때 발생할 수 있는 상황을 모두 체크하여, 최적의 수가 무엇인지 확인한다. 그리고는 dp 배열에 이를 저장하면서, 값을 반환하면 된다.

 

public class Solution {

    static int[] hps = new int[3];
    static int[][][] memory;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {//hp 값 초기화
            hps[i] = Integer.parseInt(st.nextToken());
        }

        memory = new int[hps[0] + 1][hps[1] + 1][hps[2] + 1];//dp를 위한 3중 배열 초기화
        
        for (int i = 0; i < memory.length; i++) {
            for (int j = 0; j < memory[i].length; j++) {
                Arrays.fill(memory[i][j], -1);
            }
        }

        System.out.println(check(hps[0], hps[1], hps[2]));
    }

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

        if (hp1 == 0 && hp2 == 0 && hp3 == 0) {//hp가 모두 0이라면
            return 0;
        }

        if (memory[hp1][hp2][hp3] != -1) {//해당 상황에 대한 답이 이미 계산됐다면
            return memory[hp1][hp2][hp3];
        }

        int result = 987654321;

        //모든 경우의 수를 확인해 최적의 수 확인
        result = Math.min(result, check(hp1 - 9, hp2 - 3, hp3 - 1) + 1);
        result = Math.min(result, check(hp1 - 9, hp2 - 1, hp3 - 3) + 1);
        result = Math.min(result, check(hp1 - 3, hp2 - 9, hp3 - 1) + 1);
        result = Math.min(result, check(hp1 - 3, hp2 - 1, hp3 - 9) + 1);
        result = Math.min(result, check(hp1 - 1, hp2 - 3, hp3 - 9) + 1);
        result = Math.min(result, check(hp1 - 1, hp2 - 9, hp3 - 3) + 1);

        return memory[hp1][hp2][hp3] = result;//값 저장
    }
}

결과