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

문제링크:

12869번: 뮤탈리스크

 

 

난이도: 골드4

 

 

문제:

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

 

 

문제 이해:

이 문제는 짧기에 문제를 이해하기 어렵진 않을 것이다. 바로 예제 입력 1로 이해해보자

처음에 1 3 2 순서대로 공격하면 남은 체력은  (12-9, 10-1, 4-3) = (3, 9, 1)이다 이때 2 1 3 순서대로 공격을 하면  남은 체력은(0, 0, 0)이다 즉 2번의 공격만에 모든 SCV체력을 0으로 만들었기에 2가 출력되는 것이다.

 

 

구현 방향:

먼저 “남은 체력”을 세 칸짜리 상태로 본다. SCV가 2마리거나 1마리면 빈 칸을 0으로 채워서 항상 세 칸으로 맞춘다. 한 칸이 0 이하면 그 SCV는 파괴된 것이니 0으로 취급한다.

 

각 턴은 9·3·1 피해를 서로 다른 칸에 배치하는 선택이다. 가능한 배치는 여섯 가지(9·3·1의 순열)라서, 현재 상태에서 이 여섯 가지를 모두 가정해 “다음 상태”들을 만든다. 음수가 되면 0으로 깎아 주고 진행한다.

 

그 다음은 “최소 턴”을 찾는 문제다. 현재 상태에서 한 턴을 쓴 뒤 만들어지는 여섯 개의 다음 상태 각각에 대해 같은 과정을 반복해서 필요한 턴 수를 계산하고, 그중 가장 작은 값에 방금 쓴 1턴을 더한 것이 현재 상태의 답이 된다.

 

중복 계산을 막기 위해 한 번 구한 상태의 결과는 메모해 둔다. 이후에 똑같은 상태가 다시 나오면 즉시 저장값을 돌려주므로 탐색이 급격히 빨라진다.

 

대칭 상태를 줄이기 위해 매번 세 칸을 큰 체력부터 내림차순으로 정리해 동일한 모양은 하나로 묶는다. 이렇게 하면 같은 본질의 상태를 여러 형태로 반복 계산하지 않게 된다.

 

기저는 간단하다. 세 칸이 모두 0이면 더 이상 턴이 필요 없으니 0을 반환한다. 이 원리로 예를 들면 12·10·4에서 첫 턴에 9·1·3을 배치하면 3·9·1이 되고, 다음 턴에 9·3·1을 배치하면 0·0·0이 되어 총 2턴이 된다.

 

이를 코드로 구현하면 다음과 같다.

 

 

정답코드:

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[][][] dp = new int[61][61][61]; // 체력 최대 60

    static int attack(int hp1, int hp2, int hp3){
        // 바닥 처리
        if (hp1 < 0) hp1 = 0;
        if (hp2 < 0) hp2 = 0;
        if (hp3 < 0) hp3 = 0;

        // 모두 0이면 종료
        if (hp1 == 0 && hp2 == 0 && hp3 == 0) return 0;

        // 상태 정규화(내림차순) -> 중복 상태 감소
        int[] s = {hp1, hp2, hp3};
        Arrays.sort(s);                  // 오름차순
        hp1 = s[2]; hp2 = s[1]; hp3 = s[0]; // 내림차순으로 재배치

        // 메모 체크(0은 '미방문' 의미로 쓰기 어려우니 -1을 초기값으로 사용)
        if (dp[hp1][hp2][hp3] != -1) return dp[hp1][hp2][hp3];

        // 여섯 가지 분배 모두 시도
        int r1 = attack(Math.max(hp1-9,0), Math.max(hp2-3,0), Math.max(hp3-1,0));
        int r2 = attack(Math.max(hp1-9,0), Math.max(hp2-1,0), Math.max(hp3-3,0));
        int r3 = attack(Math.max(hp1-3,0), Math.max(hp2-9,0), Math.max(hp3-1,0));
        int r4 = attack(Math.max(hp1-3,0), Math.max(hp2-1,0), Math.max(hp3-9,0));
        int r5 = attack(Math.max(hp1-1,0), Math.max(hp2-9,0), Math.max(hp3-3,0));
        int r6 = attack(Math.max(hp1-1,0), Math.max(hp2-3,0), Math.max(hp3-9,0));

        // 이번 공격 1회 + 다음 상태의 최소
        int best = Math.min(Math.min(r1,r2), Math.min(r3,r4));
        best = Math.min(best, Math.min(r5,r6));
        return dp[hp1][hp2][hp3] = 1 + best;
    }

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

        int x=0, y=0, z=0;
        if (N >= 1) x = Integer.parseInt(st.nextToken());
        if (N >= 2) y = Integer.parseInt(st.nextToken());
        if (N == 3) z = Integer.parseInt(st.nextToken());

        // dp 초기화
        for (int i=0;i<=60;i++)
            for (int j=0;j<=60;j++)
                Arrays.fill(dp[i][j], -1);

        System.out.println(attack(x, y, z));
    }
}

 

짧은 추적 예시:

시작: attack(10,7,2)

• 정렬 → (10,7,2), dp 비어 있음
• r1로 하위 호출: attack(1,4,1) → 정렬 (4,1,1), dp 비어 있음
  • 그 안에서 또 r1: attack(0,0,0) → 0 반환(기저)
  • (4,1,1) 호출은 이제 r1..r6 최솟값이 0이니 dp[4][1][1]=1 저장 후 1 반환
• 최상위 (10,7,2)는 r1=1을 받음(다른 가지도 보겠지만 대개 이것이 최소) →
  dp[10][7][2]=2 저장 후 2 반환

다음에 attack(4,1,1)이나 attack(10,7,2)가 또 호출되면?
→ dp에 이미 저장되어 있어서 바로 return, 더 안 내려간다.

 

 

감사합니다.