C++) 백준 12869 뮤탈리스트

문제

 

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.

각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.

뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.

1. 첫 번째로 공격받는 SCV는 체력 9를 잃는다.
2. 두 번째로 공격받는 SCV는 체력 3을 잃는다.
3. 세 번째로 공격받는 SCV는 체력 1을 잃는다.

SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.

남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

힌트 : 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다.

 

코드

 

#include<algorithm>
#include<iostream>
#include<vector>
#include<tuple>
#include<queue>

using namespace std;

int dist[61][61][61];


int main()
{
	vector<int> mutalisk = { 1,3,9 };
	queue < tuple<int, int, int>> Q;
	int scv[3] = { 0 };
	int n;

	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> scv[i];

	Q.push({ scv[0],scv[1],scv[2] });
	while (!dist[0][0][0]) {

		tuple<int, int, int> t = Q.front(); Q.pop();

		do {
			int a = get<0>(t) - mutalisk[0] < 0 ? 0 : get<0>(t) - mutalisk[0];
			int b = get<1>(t) - mutalisk[1] < 0 ? 0 : get<1>(t) - mutalisk[1];
			int c = get<2>(t) - mutalisk[2] < 0 ? 0 : get<2>(t) - mutalisk[2];

			if (dist[a][b][c] != 0) continue;

			dist[a][b][c] = dist[get<0>(t)][get<1>(t)][get<2>(t)] + 1;
			Q.push({ a,b,c });

		} while (next_permutation(mutalisk.begin(), mutalisk.end()));
	}
	cout << dist[0][0][0];
}

 

풀이

 

<접근1>
DP 방식으로 풀어 나가보려 하였지만, 몇 시간을 고민하여도 해결책이 나오지 않았다.
DP 공부가 더 필요하다고 느껴졌다.
나름 하드코딩을 통해 찾아보려고 직접 조건을 달며 접근해보았지만 너무 복잡했다.

 

<접근2>
먼저, 단계별로 최소의 경우를 찾아가보려 하였다.
하지만 문제는 아무리 봐도 모든 경우에서 최적을 찾아야 할 것 같았다.
여러 시도 끝에, 결국 BFS를 쓰기로 하였다.

 

<접근3>
문제가 BFS로 풀린다는 정보도 미리 알고 있었고, 어떻게 접근해야 할 지도 바로 보였다.
Distance BFS를 사용하여 접근하였다.
튜플을 사용하여 3차원 배열로 SCV의 체력의 경우의 수를 표현한다.
BFS를 통해 최적의 수를 찾아가며 SCV들의 체력이 0이 되는 경우에 반복을 종료한다.