BOJ)12869 뮤탈리스크

문제:icpc.me/12869

3개의 SCV의 체력이 주어질 때 뮤탈리스크가 각 SCV를 서로 다른 공격으로 공격할 때 공격횟수의 최솟값을 출력하는 문제이다.

이 문제는 그리디하게 힘들다고 생각한 순간 동적 계획법을 떠올릴 수 있다.

하지만 공격횟수로 테이블을 잡기 애매하기 때문에 각 SCV의 체력에 포커스를 맞춘다면 

dp[x][y][z] = 체력이 x , y ,z 인 SCV를 파괴하는데 필요한 최소 공격 횟수로 테이블을 세울 수 있고

점화식은 공격가능한 6가지 방법 중에 최솟값을 호출하면 된다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 987654321
using namespace std;
int dp[66][66][66];
int n, a, b, c;
int func(int x, int y, int z) {
    if (!x&&!y&&!z)return 0;
    int &ret = dp[x][y][z];
    if (ret != -1)return ret;
    ret = INF;
    ret = min(ret, func(max(0, x - 9), max(0, y - 3), max(0, z - 1)) + 1);
    ret = min(ret, func(max(0, x - 9), max(0, y - 1), max(0, z - 3)) + 1);
    ret = min(ret, func(max(0, x - 3), max(0, y - 9), max(0, z - 1)) + 1);
    ret = min(ret, func(max(0, x - 1), max(0, y - 9), max(0, z - 3)) + 1);
    ret = min(ret, func(max(0, x - 3), max(0, y - 1), max(0, z - 9)) + 1);
    ret = min(ret, func(max(0, x - 1), max(0, y - 3), max(0, z - 9)) + 1);
    return ret;
}
int main() {
    memset(dp, -1, sizeof(dp));
    scanf("%d", &n);
    scanf("%d%d%d", &a, &b, &c);
    printf("%d\n", func(a, b, c));
    return 0;
}