백준 12869번 뮤탈리스크

문제 링크입니다: https://www.acmicpc.net/problem/12869

12869번: 뮤탈리스크

 

주어진 N과 SCV의 최대 체력이 크지 않기 때문에 브루트포스로 풀어도 되는 문제였습니다.

visited set의 키를 {scv 체력의 순열, 몇 번째 공격}으로 두는 것이 핵심이었습니다.

억지로 푼 느낌...

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <set>
	using namespace std;
	const int INF = 987654321;
	const int MAX = 3;
	int result = INF;
	vector<int> scvs(MAX);
	set<pair<vector<int>, int>> visited;
	bool allDestroyed(vector<int> &scvs)
	{
	for (int i = 0; i < MAX; i++)
	{
	if (scvs[i])
	{
	return false;
	}
	}
	return true;
	}
	void func(int cnt, vector<int> scvs)
	{
	if (allDestroyed(scvs))
	{
	result = min(result, cnt);
	return;
	}
	vector<int> multalisk;
	multalisk.push_back(1);
	multalisk.push_back(3);
	multalisk.push_back(9);
	visited.insert({ scvs, cnt });
	do
	{
	vector<int> copyScvs(MAX);
	for (int i = 0; i < MAX; i++)
	{
	copyScvs[i] = scvs[i];
	scvs[i] = max(scvs[i] - multalisk[i], 0);
	}
	if (visited.find({ scvs, cnt + 1 }) == visited.end())
	{
	func(cnt + 1, scvs);
	}
	for (int i = 0; i < MAX; i++)
	{
	scvs[i] = copyScvs[i];
	}
	} while (next_permutation(multalisk.begin(), multalisk.end()));
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
	cin >> scvs[i];
	}
	func(0, scvs);
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2022

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~