[G5] 백준 20008번 몬스터를 처치하자! C++ 백트래킹

리뷰

 

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

스킬을 사용해 가장 빠른 시간 내에 몬스터를 처치하는 시간을 구하는 문제

 

 

전역 변수

• n : 스킬의 개수를 저장할 변수
• ans : 몬스터를 처치한 가장 빠른 시간을 저장할 변수
• T : 스킬의 사용이 가능한 시간을 저장할 배열
• Skill : 스킬의 쿨타임 ct와 데미지 dam을 정의할 구조체
• skills : 스킬 정보를 담기 위한 Skill타입 배열

 

함수

1. bt

void bt(int level, int remain)

 

백트래킹을 통해 스킬을 사용해 몬스터를 공격하는 경우의 수를 구하는 함수

1. 매개 변수로 재귀 레벨(소요 시간), 몬스터의 남은 체력 remain을 전달받는다.
2. 첫 번째 기저 조건으로 level이 ans이상일 경우 더 이상 탐색할 필요가 없으므로 리턴해준다.
3. 두 번째 기저 조건으로 remain이 0이하일 경우 ans를 level과 비교해 더 작은 값으로 저장해 준 뒤 리턴해준다.
4. 공격 여부를 체크하기 위한 변수 att를 false로 초기화 해준다.
5. n개의 스킬 정보를 순회하며 해당 스킬 인덱스의 T배열의 값이 level보다 클 경우 continue처리해 준다.
6. 스킬 사용이 가능하다면 우선 변수 curT에 현재 스킬 인덱스의 T배열 값을 저장해 준다.
7. att를 true로 바꾼 후 현재 인덱스의 T배열 값을 level + 스킬의 쿨타임으로 저장해 준다.
8. 소요시간을 올리고 몹의 체력을 스킬의 데미지만큼 깎은 후 bt함수를 통해 재귀를 진행한다.
9. 재귀를 빠져나오면 현재 인덱스의 T배열 값을 curT로 다시 복구해 준다.
10. 모든 스킬을 순회했으나 att가 false인 경우 사용할 수 있는 스킬이 없는 것이므로 소요시간만 늘리고 재귀를 진행한다.

 

문제풀이

1. 몹의 초기 체력을 담을 변수 hp를 초기화 하고, n, hp에 값을 입력 받아준다.
2. n개의 스킬 정보를 skills배열에 입력 받아 각 스킬의 쿨타임과 데미지를 저장해 준다.
3. bt 함수에 초기 값 0, hp를 매개변수로 전달하여 백트래킹을 진행한다.
4. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• T배열을 원복해 줄 때 스킬의 쿨타임 만큼 빼주는게 아닌 이전 값으로 복구해 주어야 한다.

 

정답 코드

#include<iostream>
using namespace std;

int n, ans = 2e9;
int T[5];
struct Skill {
	int ct, dam;
};
Skill skills[5];

void bt(int level, int remain) {
	if (ans <= level) return;
	if (remain <= 0) {
		ans = min(ans, level);
		return;
	}

	bool att = false;
	for (int i = 0; i < n; ++i) {
		if (T[i] > level) continue;
		int curT = T[i];
		att = true;
		T[i] = level + skills[i].ct;
		bt(level + 1, remain - skills[i].dam);
		T[i] = curT;
	}

	if (!att) bt(level + 1, remain);
}

int main() {
	int hp;
	cin >> n >> hp;
	for (int i = 0; i < n; ++i) {
		cin >> skills[i].ct >> skills[i].dam;
	}

	bt(0, hp);
	cout << ans;
}