12869번: 뮤탈리스크

문제링크: 12869번: 뮤탈리스크

문제

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

설명

처음에는 DP테이블을 무엇으로 잡아야할지 헷갈려했다. DP테이블을 'scv의 남은 체력이 a,b,c일 때 남은 최소 공격 횟수'를 DP테이블로 잡는다면 문제가 쉽게 해결된다.

주의해야 할 점은 scv가 고정적으로 3마리가 아니라는점과 데미지(9,3,1)의 조합에 따라 6가지의 분기가 나온다는 점이다. scv가 3마리가 아닐경우 체력을 0으로 고정하였고 6가지 분기는 직접 하나씩 만들어 주었다.

코드

#include <iostream>
#include <algorithm>
#define endl '\n'
#define MAX 61
#define INF 1000000

using namespace std;

int dp[MAX][MAX][MAX];

int getDP(int a, int b, int c) {
	int& ret = dp[a][b][c];
	if (ret != INF) return ret;

	int nextA = a, nextB = b, nextC = c;

	// 1
	nextA = max(a - 9, 0), nextB = max(b - 3, 0), nextC = max(c - 1, 0);
	ret = min(ret, getDP(nextA, nextB, nextC) + 1);

	// 2
	nextA = max(a - 9, 0), nextB = max(b - 1, 0), nextC = max(c - 3, 0);
	ret = min(ret, getDP(nextA, nextB, nextC) + 1);

	// 3
	nextA = max(a - 3, 0), nextB = max(b - 1, 0), nextC = max(c - 9, 0);
	ret = min(ret, getDP(nextA, nextB, nextC) + 1);

	// 4
	nextA = max(a - 3, 0), nextB = max(b - 9, 0), nextC = max(c - 1, 0);
	ret = min(ret, getDP(nextA, nextB, nextC) + 1);

	// 5
	nextA = max(a - 1, 0), nextB = max(b - 3, 0), nextC = max(c - 9, 0);
	ret = min(ret, getDP(nextA, nextB, nextC) + 1);

	// 6
	nextA = max(a - 1, 0), nextB = max(b - 9, 0), nextC = max(c - 3, 0);
	ret = min(ret, getDP(nextA, nextB, nextC) + 1);

	return ret;
}

void solve() {
	int N;
	int scv[3] = { 0,0,0 };
	for (int i = 0; i < MAX; ++i) {
		for (int j = 0; j < MAX; ++j) {
			for (int k = 0; k < MAX; ++k) {
				dp[i][j][k] = INF;
			}
		}
	}
	cin >> N;
	for (int i = 0; i < N; ++i)
		cin >> scv[i];
	dp[0][0][0] = 0;

	cout << getDP(scv[0], scv[1], scv[2]);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	//freopen("input.txt", "r", stdin);
	solve();
	return 0;
}