[baekjoon 16434] 드래곤 앤 던전 (이분탐색 + 구현) (C++)

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

16434번: 드래곤 앤 던전

용사가 던전을 지나가면서, 몬스터를 만나면 몬스터와 대결을 하고 체력 포션을 먹으면 회복이 되는 구현 문제이다.

이 과정을 진행할 수 있는 최소한의 hp를 구하는 문제다.

 

우선, 문제를 읽어보니 step의 n은 10만이었고, 체력의 MAX는 주어지지 않았다.

이 과정에서, 어떻게 최솟값을 구할지를 생각했다.

x를 정해두고 매 단계 빼고, 더하고 하려고 했지만 최대 hp를 모르는 상태에서는 불가능했다.

포션을 먹으면서 hp가 회복될 때, 최대 hp이상은 회복을 못 시키기 때문이다.

 

따라서, 최대 hp를 일단 정한 다음 던전을 돌아야 한다고 생각했다.

그렇다면 최대 hp를 어떻게 정할까?

만약 백만의 공격력을 갖고 있는 백만 hp의 던전을 N(123456)의 최대만큼 만나면서, 용사의 공격력은 1이라면

이 던전을 클리어하기 위한 최대 hp는 매우 커져야 한다.

999999 * 1,000,000 * 123456 이므로 이미 int의 범위를 넘어간다.

따라서 O(N)으로 접근하면 무조건 시간 초과가 나고, 따라서 logN으로 접근해야 한다.

log 수준으로 수의 범위를 줄여나가면서 값을 대입해보는 파라매트릭 서치라는 결과가 나왔다.

42억 * 42억 = 2^64이므로 값이 아무리 커도, 이분 탐색으로 하면 64번도 안돼서 탐색이 가능하다.

 

따라서 O(N) * 최대 N(123456)을 O(logN) * 최대 N(123456)으로 줄였다.

= 이분 탐색으로 값을 구한 뒤, 매번 던전을 통과하는 횟수

 

구현은 간단하다. 이분 탐색 코드와 던전을 진행하는 함수를 구현했다.

추가적으로, 진행 시 체력 계산 시 int형으로 선언하면 오버플로우가 나서 제대로 계산이 되지 않는다.

웬만하면 다 long long으로 바꾸고 풀었다.

#include <iostream>
#include <vector>
#define MAX 999999000001

using namespace std;

typedef pair<int, pair<int, int>> ppii;
typedef long long ll;

vector<ppii> v;
int n, h_atk, t, a, h;

bool progress(ll target) {
	ll max_hp = target;
	ll cur_hp = target;
	ll temp_atk = h_atk;

	for (int i = 0; i < v.size(); i++) {
		ll status = v[i].first;
		ll attack = v[i].second.first;
		ll hp = v[i].second.second;

		if (status == 1) {
			ll cnt = hp / temp_atk;
			if (hp % temp_atk == 0)
				cnt--;
			ll attackAmount = cnt * attack;
			cur_hp -= attackAmount;
			if (cur_hp <= 0) {
				return false;
			}
		}
		else {
			temp_atk += attack;
			cur_hp += hp;
			if (cur_hp > max_hp) {
				cur_hp = max_hp;
			}
		}
	}
	return true;
}

int main() {
	cin >> n >> h_atk;
	for (int i = 0; i < n; i++) {
		cin >> t >> a >> h;
		v.push_back({ t,{a, h} });
	}

	ll l = 1;
	ll r = MAX * n;
	ll answer = 0;

	while (l <= r) {
		ll mid = (l + r) / 2;
		if (progress(mid)) {
			answer = mid;
			r = mid - 1; // 최소의 체력 구하기
		}
		else {
			l = mid + 1; // 체력이 더 필요
		}
	}

	cout << answer;
}