Baekjoon 12869번 뮤탈리스크

문제

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

걸린 시간

02 : 16 : 12

풀이

C++

#include <iostream>
#include <string.h>
#include <algorithm>
#define INF 987654321
using namespace std;

int n;
int scv[3] = {0, 0, 0};
int damage[3] = {9, 3, 1};
int cache[121][121][121];

int dp(int h[3], int a) { // health, attack
    // 기저 사례
    if(h[0] <= 0 && h[1] <= 0 && h[2] <= 0)
        return a;
    // 메모이제이션
    int& ret = cache[h[0]+60][h[1]+60][h[2]+60];
    if(ret != -1)
        return ret;
    // 재귀 호출
    ret = 60;
    for(int i = 0; i < 3; i++) {
        int one = i;
        if(h[one] >= 0){
            h[one] -= damage[0];
            for(int j = 0; j < 2; j++) {
                int two = (i+1+j%2)%3;
                int three = (i+1+(j+1)%2)%3;
                    h[two] -= damage[1];
                    h[three] -= damage[2];
                    ret = min(ret, dp(h, a+1));
                    h[two] += damage[1];
                    h[three] += damage[2];
            }
            h[one] += damage[0];
        }
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> scv[i];
    memset(cache, -1, sizeof(cache));
    cout << dp(scv, 0);
    return 0;
}

재귀 호출 구현에 꽤 많은 시간이 걸린 문제.

모든 scv 의 체력이 0이 되기 위한 최소 경우의 수를 구해야하므로 각 scv 체력을 상태로 하는 배열에 최소 경우의 수를 메모이제이션 하면 시간 내에 통과할 수 있다.