백준 16434번 드래곤 앤 던전

문제

용사는 공주를 구하기 위해 무시무시한 용이 있는 던전으로 향하기로 하였습니다. 우선 용사는 용사 자신과 던전을 분석하였습니다.

용사에게는 세 종류의 능력치가 있습니다. 

• HMaxHP : 용사의 최대 생명력입니다. 이 값은 1이상이어야 하며 던전에 들어간 이후로 변하지 않습니다.
• HCurHP : 현재 용사의 생명력입니다. 던전에 들어가기 전 이 값은 용사의 최대 생명력 HMaxHP와 같습니다. 이 값은 HMaxHP보다 커질 수 없습니다.
• HATK : 용사의 공격력입니다.

던전은 총 N개의 방으로 이루어져 있고 i번째 방을 통해서만 i+1번째 방으로 이동 할 수 있습니다. 방에는 포션이 있거나 몬스터가 있는데 몬스터가 있을 경우 몬스터를 쓰러트려야지 다음방으로 이동 할 수 있습니다. N번째 방에는 공주와 용이 있고, 용을 무찌르면 공주를 구할 수 있습니다.

몬스터가 있는 방에 올 경우 다음과 같이 전투가 진행됩니다.

1. 용사의 공격력 HATK만큼 몬스터의 생명력을 깎습니다.
2. 몬스터의 생명력이 0 이하이면 전투가 종료되고 용사는 다음 방으로 이동합니다.
3. 몬스터의 공격력만큼 용사의 생명력 HCurHP를 깎습니다.
4. 용사의 생명력이 0 이하이면 전투가 종료되고 용사는 사망합니다.
5. 다시 1부터 진행합니다.

포션이 있는 방에 올 경우 포션을 마셔서 현재 용사의 생명력 HCurHP가 일정량 회복되고 공격력 HATK도 일정량만큼 증가됩니다. 회복된 생명력이 최대 생명력 HMaxHP보다 큰 경우 용사의 현재 생명력 HCurHP가 최대 생명력 HMaxHP와 같아집니다.

용사는 던전으로 향하기 전에 만반의 준비를 하고 있습니다. 용사는 수련을 하면 최대 생명력 HMaxHP를 늘릴 수 있는데 얼마나 수련해야 할지 고민입니다.

용사는 N번 방에 있는 용을 쓰러트리기 위한 최소의 HMaxHP를 여러분이 계산해주면 좋겠다고 합니다.

문제풀이

사용한 알고리즘 : 이분탐색

(0) 생각

 x라는 체력으로 용사가 용을 쓰러트리기 가능한지는 O(N)으로 가능할 겁니다.

 N = 10^5 이니 최대 생명력을 알아보는데 log(N) 의 방법이 필요하다고 생각할 수 있고, 그 방법이 이분탐색입니다.

(1) 코드 50~60

 최대 생명력을 이분탐색으로 구현해줍니다.

 생명력의 범위를 문제에서 따로 주지 않았으므로, 적당히 큰 생명력을 최대로, 0을 최소로 설정 후 이분탐색 해주었습니다.

(2) 코드 20~38

 x 라는 생명력으로 용을 물리칠 수 있는지 판단하는 재귀함수입니다.

 각 단계의 용을 죽여야 다음 단계로 진행할 수 있음을 생각해줍니다.

	#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	int N, H_ATK;
	struct Room {
	int T;
	ll A;
	ll H;
	Room() {
	T = 0;
	A = 0;
	H = 0;
	}
	Room(int t1, ll a1, ll h1) : T(t1), A(a1), H(h1) {}
	};
	Room arr[222222];
	bool path(int curr, ll atk, ll hp, ll origin_hp) {
	if (curr == N) return true;
	int t = arr[curr].T;
	ll a = arr[curr].A;
	ll h = arr[curr].H;
	if (t == 1) {
	ll cnt = h / atk + (h % atk > 0); // 용사가 공격해야 하는 횟수
	hp -= a * (cnt - 1); // 용사도 공격 받아야함...
	if (hp <= 0) return false; // 용사체력으로는 공격 받은거 못버팀
	return path(curr + 1, atk, hp, origin_hp); // 버팀
	}
	else {
	atk += a;
	hp = min(hp + h, origin_hp);
	return path(curr + 1, atk, hp, origin_hp);
	}
	}
	int main() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> H_ATK;
	for (int i = 0; i < N; ++i) {
	int t;
	ll a, h;
	cin >> t >> a >> h;
	arr[i] = Room(t, a, h);
	}
	ll ans = 0LL;
	ll l = 0LL;
	ll r = 1987654321987654321LL;
	while (l <= r) {
	ll mid = (l + r) / 2LL;
	if (path(0, H_ATK, mid, mid)) {
	ans = mid;
	r = mid - 1;
	}
	else l = mid + 1;
	}
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 16434.cpp hosted with ❤ by GitHub