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

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

12869번: 뮤탈리스크

 

풀이

---

DP로 푸는 문제다.

모든 경우의 수를 탐색해서 제일 빨리 SCV를 다 처치하는 경우를 찾는다

코드

---

#include <iostream>
#include <queue>
#include <memory.h>
#include <string>
#include <vector>
#include <math.h>
using namespace std;
#define MAX 987432
int N;
int SCVHP[4];
int SCV[61][61][61];

int n = 0;
void Mutalisk(int scv1HP,int scv2HP, int scv3HP,int count) {
	if (SCV[scv1HP][scv2HP][scv3HP] <= count)
		return;

	SCV[scv1HP][scv2HP][scv3HP] = count;
	if (scv1HP == 0 && scv2HP == 0 && scv3HP == 0)
		return;
	
	Mutalisk(max(scv1HP - 9, 0), max(scv2HP - 3, 0), max(scv3HP - 1, 0), count + 1);
	Mutalisk(max(scv1HP - 9, 0), max(scv2HP - 1, 0), max(scv3HP - 3, 0), count + 1);
	Mutalisk(max(scv1HP - 3, 0), max(scv2HP - 9, 0), max(scv3HP - 1, 0), count + 1);
	Mutalisk(max(scv1HP - 1, 0), max(scv2HP - 9, 0), max(scv3HP - 3, 0), count + 1);
	Mutalisk(max(scv1HP - 3, 0), max(scv2HP - 1, 0), max(scv3HP - 9, 0), count + 1);
	Mutalisk(max(scv1HP - 1, 0), max(scv2HP - 3, 0), max(scv3HP - 9, 0), count + 1);
	return;
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> SCVHP[i];
	}
	
	memset(SCV, MAX, sizeof(SCV));;
	Mutalisk(SCVHP[0], SCVHP[1], SCVHP[2], 0);
	cout << SCV[0][0][0] << endl ;
	return 0;
}