[백준/C++] 20008 몬스터를 처치하자!

 

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

20008번: 몬스터를 처치하자!

문제 분석

난이도

골드 5

분류

브루트포스, 백트래킹

들어가기 전에

문제를 제대로 읽지 않으면 매개변수탐색으로 오해할 수 있는 문제.
스킬을 동시에 사용하는 것이 아니었다면 전형적인 매개변수탐색 문제였을 것이다.

문제 풀이

 

풀이

간단하게 백트래킹을 떠올릴 수 있다. N도 수가 작고, D가 충분히 크기 때문에 (HP의 1/10) 스킬의 최대 사용횟수는 10회일 것이다. 쿨타임 또한 1~10 정도이고 쿨타임도 각각 다르기 때문에 시간초과 걱정 없이 편하게 코드를 짜도 될 것이다.

소스코드

 

#include <iostream>

using namespace std;

int n,hp;
int matrix[5][2];
int cool[5] = {0,};
int ans = 100000000;

int bt(int time, int damage)
{
	if (damage >= hp)
	{
		ans = min(ans, time);
		return 0;
	}
	bool use=false;
	for (int i = 0; i < n; i++)
	{
		if (cool[i] <= time)
		{
			use = true;
			int tmp = cool[i];
			cool[i] = time + matrix[i][0];
			bt(time + 1, damage + matrix[i][1]);
			cool[i] = tmp;
		}
	}
	if (!use) bt(time + 1, damage);
	return 0;
}

int main()
{
	cin >> n >> hp;
	for (int i = 0; i < n; i++) cin >> matrix[i][0] >> matrix[i][1];
	bt(0, 0);
	cout << ans;
}