[BOJ/Gold 5] 백준 20008 몬스터를 처치하자!(C++)

문제 링크

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

 

문제

가장 빠른 시간 내에 몬스터를 처치하려고 한다. 사용할 수 있는 스킬은 N개 있으며, 각 스킬은 사용하는 데 1초가 들고, 사용을 시작한 지 1초 후 몬스터에게 일정 대미지를 입힌다. 여러 개의 스킬을 동시에 사용할 수는 없다.

각 스킬에는 저마다의 대기 시간과 대미지가 있다. 대기 시간은 스킬을 사용하기 시작한 순간부터 차기 시작한다.

예를 들어, 현재 시각이 t = 0이고, 대기 시간이 10초이고 대미지가 10인 스킬을 체력이 100인 몬스터에게 사용했다고 하자. 그러면 t = 1일 때 몬스터의 체력이 90으로 줄어들고, 같은 스킬은 t = 10일 때부터 다시 사용할 수 있다.

 

입력

첫 번째 줄에는 스킬 개수 N(1 ≤ N ≤ 5)과 몬스터의 체력(HP)을 나타내는 정수(1 ≤ HP ≤ 100000)가 주어진다.

두 번째 줄부터는 줄마다 스킬의 대기 시간을 초 단위로 나타내는 정수 C(1 ≤ C ≤ 10)와 스킬의 대미지를 나타내는 정수 D(HP/10 ≤ D ≤ HP)가 공백을 두고 주어진다. 모든 스킬의 대기 시간은 다르며, 모든 D의 합은 HP보다 작다.

 

출력

몬스터를 처치하는 데 걸리는 최소 시간을 출력한다.

 

예제 입력 1

2 70000
3 10000
5 10001

예제 출력 1

12

 

시간	0초	1초	2초	3초	4초	5초	6초	7초	8초	9초	10초	11초	12초
mob hp	70000	59999	49999	49999	49999	39999	29998	29998	19998	19998	19998	9997	-3
남은 대기시간 (3 10000)	0	0->3	2	1	0->3	2	1	0->3	2	1	0	0->3	2
남은 대기시간 (5 10001)	0->5	4	3	2	1	0->5	4	3	2	1	0->5	0	0

예제 입력 2

2 70000
3 10001
5 10000

예제 출력 2

12

 

시간	0초	1초	2초	3초	4초	5초	6초	7초	8초	9초	10초	11초	12초
mob hp	70000	60000	49999	49999	49999	39998	29998	29998	19997	19997	19997	9996	-4
남은 대기시간 (3 10001)	0	0->3	2	1	0->3	2	1	0->3	2	1	0->3	0	1
남은 대기시간 (5 10000)	0->5	4	3	2	1	0->5	4	3	2	1	0	0->5	4

예제 입력 3

3 2831
7 1138
6 507
9 870

예제 출력 3

7

 

알고리즘 분류

• 백트래킹

 

풀이

늘 있는 백트래킹이지만 쿨타임을 돌리면 스킬을 다시 사용할 수 있으므로, 현재 스킬을 사용하면 기록해야 할 것은 해당 스킬을 다시 사용할 수 있는 최소의 시간이다.

재귀가 끝나고 현재 시간으로 돌아오면, 현재 스킬을 사용하지 않는 방향으로 다시 재귀를 시작할 것이고, 갱신해 둔 스킬 재사용이 가능한 시간을 다시 원래대로 갱신해야 한다. 따라서 기록 방식은 다음과 같다.

• 가장 최근에 기록해 둔, 해당 스킬의 재사용 가능한 시간을 변수 하나를 선언해서 따로 저장한다.
• 해당 스킬의 재사용 가능한 시간을 새로 기록하고, 재귀를 수행한다.
• 재귀가 끝나면 따로 저장해 둔 원래 시간 값을 다시 해당 스킬의 재사용 가능한 시간으로 갱신한다.

 

모든 스킬이 쿨타임이라 사용 가능한 스킬이 없다면 그냥 시간을 1초 더하고 재귀를 수행한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 6
#define INF 2e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, HP;
int C[MAX], D[MAX], T[MAX];
int Answer = INF;

void input() {
	cin >> N >> HP;
	for (int i = 0; i < N; i++) {
		cin >> C[i] >> D[i];
	}
}

void dfs(int Time, int NowHP) {
	if (Time > Answer) {
		return;
	}
	if (NowHP <= 0) {
		Answer = min(Answer, Time);
		return;
	}

	bool Flag = false;

	for (int i = 0; i < N; i++) {
		if (T[i] <= Time) {
			Flag = true;
			int Prev = T[i];
			T[i] = Time + C[i];
			dfs(Time + 1, NowHP - D[i]);
			T[i] = Prev;
		}
	}

	if (!Flag) {
		dfs(Time + 1, NowHP);
	}
}

void settings() {
	dfs(0, HP);
}

void printAnswer() {
	cout << Answer << "\n";
}

int main() {
    FASTIO

	input();
	settings();
	printAnswer();

    return 0;
}