[백준] 12869번 - 뮤탈리스크 / C++

문제

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

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int N;
int damage[3] = {9, 3, 1};
int d[61][61][61];

int dp(vector<int> scv)
{
	int i, res = 99;
	vector<int> tmp;

	// 순열을 사용하기 위해 정렬
	sort(scv.begin(), scv.end());
	do
	{
		// 이미 확인된 케이스인 경우 결과값 갱신
		if (d[scv[0]][scv[1]][scv[2]] != -1)
		{
			res = min(res, d[scv[0]][scv[1]][scv[2]]);
		}
		// 아직 확인되지 않은 케이스인 경우
		else
		{
			// tmp 벡터에 공격 후 값을 저장
			// 공격 후 값이 음수인 경우 0을 저장
			tmp.clear();
			for (i = 0; i < scv.size(); i++)
			{
				tmp.push_back(max(scv[i] - damage[i], 0));
			}
			// dp 수행 후 결과값 갱신
			d[scv[0]][scv[1]][scv[2]] = dp(tmp) + 1;
			res = min(res, d[scv[0]][scv[1]][scv[2]]);
		}	
	} while (next_permutation(scv.begin(), scv.end()));
	return res;
}

int main()
{
	int i, tmp;
	vector<int> scv;

	cin >> N;
	for (i = 0; i < N; i++)
	{
		cin >> tmp;
		scv.push_back(tmp);
	}
	memset(d, -1, sizeof(d));	// 초기화
	d[0][0][0] = 0;			// 모두 0인 경우 추가적인 공격이 필요하지 않으므로 0을 저장
	cout << dp(scv) << endl;	// dp 수행
	return 0;
}

 

링크

12869번: 뮤탈리스크

inbdni/Baekjoon