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

스타크래프트를 즐겨하는 사람으로서 뮤탈리스크란 문제를 보고 호기심때문에 풀어봤다. 

(난 테란 유저이기 때문에 뮤탈리스크를 매우 싫어한다.) 

 

1. 사기 유닛 뮤탈리스크는 소중한 SCV를 최대 3마리까지 공격 가능하다. 순서에 따른 공격 데미지는 총 6가지의 경우가 있으므로 이차원 벡터에 저장하였다. 

2. 최대 3마리까지 공격 가능하니 3차원 dp배열을 생성하여 해당 배열에 최소 공격횟수를 저장해준다. 

3. 이후 다른 재귀에서 해당 dp배열을 참조할 시 기록해 뒀던 값을 반환하여 사용하면 된다. 

 

* 본인은 next_permutation 함수를 활용하여 완전 탐색으로 구현을 시도했지만 시간 초과가 발생하여 3차원 DP를 활용하였다. 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <climits>
using namespace std; 
int n; 
int dp[61][61][61]; 
int hp[3];
vector <vector<int>> v = {
	{1,3,9},
	{1,9,3},
	{3,1,9},
	{3,9,1},
	{9,1,3},
	{9,3,1}
};
int solution(int x, int y, int z) {
	if (x == 0 && y == 0 && z == 0)return 0;
	else if (x < 0)return solution(0, y, z); 
	else if (y < 0)return solution(x, 0, z); 
	else if (z < 0)return solution(x, y, 0); 
	int& res = dp[x][y][z]; 
	if (res != -1)return res; 
	res = INT_MAX; 
	for (int i = 0; i < 6; i++) {
		res = min(res, solution(x - v[i][0], y - v[i][1], z - v[i][2]) + 1); 
	}
	return res; 
}
int main() {
	cin >> n; 
	memset(dp, -1, sizeof(dp)); 
	for (int i = 0; i < n; i++) cin >> hp[i]; 
	cout << solution(hp[0], hp[1], hp[2]) << "\n"; 
	return 0; 
}

12869번: 뮤탈리스크