[BOJ] 12869 뮤탈리스크 - 완전탐색

[BOJ 12869] 뮤탈리스크

뮤탈리스크 컨트롤은 테란전에서 매우 중요하다.

문제에서 제시한 최대 SCV는 3마리 이다.

세마리의 SCV가 있다고 하자.

뮤탈의 쓰리쿠션 공격 방법은 모두 6가지 이다.

 

A -> B -> C

A -> C -> B

B -> A -> C

B -> C -> A

C -> A -> B

C -> B -> A

 

이 6 가지 경우로 재귀호출을 계속 하게 되면 언젠가 SCV 3마리의 체력이 모두 0이하가 될 것이다.

재귀 호출의 Depth 자체가 공격회수와 같다고 볼수있으므로,

이를 비교해 최소값을 구하면 된다. 

 

코드를 구현하면 다음과 같다.

SCV의 체력이 음수가 될수 있음에 유의한다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>

int Max = 0x7FFFFFFF;

using namespace std;
int Hp[61][61][61];

int RecursiveMutal(int A, int B, int C)
{
	if (A == 0 && B == 0 && C == 0)
		return 0;

	if (Hp[A][B][C] != -1)
		return Hp[A][B][C];

	int Ret = Max;
	Ret = min(Ret, RecursiveMutal( A - 1 < 0 ? 0 : A - 1,  B - 3 < 0 ? 0 : B - 3,  C - 9 < 0 ? 0 : C - 9) + 1);
	Ret = min(Ret, RecursiveMutal( A - 1 < 0 ? 0 : A - 1,  B - 9 < 0 ? 0 : B - 9,  C - 3 < 0 ? 0 : C - 3) + 1);
	Ret = min(Ret, RecursiveMutal( A - 3 < 0 ? 0 : A - 3,  B - 1 < 0 ? 0 : B - 1,  C - 9 < 0 ? 0 : C - 9) + 1);
	Ret = min(Ret, RecursiveMutal( A - 3 < 0 ? 0 : A - 3,  B - 9 < 0 ? 0 : B - 9,  C - 1 < 0 ? 0 : C - 1) + 1);
	Ret = min(Ret, RecursiveMutal( A - 9 < 0 ? 0 : A - 9,  B - 1 < 0 ? 0 : B - 1,  C - 3 < 0 ? 0 : C - 3) + 1);
	Ret = min(Ret, RecursiveMutal( A - 9 < 0 ? 0 : A - 9,  B - 3 < 0 ? 0 : B - 3,  C - 1 < 0 ? 0 : C - 1) + 1);
	Hp[A][B][C] = Ret;
	return Ret;
}

int main()
{
	int RemainHp[3] = { 0 , };
	int NumScv = 0;

	memset(Hp, -1, sizeof(Hp));
	
	std::cin >> NumScv;

	for (int i = 0; i < NumScv; ++i)
		std::cin >> RemainHp[i];

	std::cout << RecursiveMutal(RemainHp[0], RemainHp[1], RemainHp[2]);
	return 0;
}