[백준/C++] 16434 드래곤 앤 던전

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

코드

#include <iostream>
#include <vector>
using namespace std;

#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL);

typedef long long ll;
typedef struct {
	ll t; 
	ll a;
 	ll h; 
} room;
vector<room> r;
ll n, h;

bool simul(ll m) {
	ll ca = h;
	ll ch = m;
	ll tmp;
	for (int i = 0; i < n; i++) {
		if (r[i].t == 1) {
			ll ma = r[i].a;
			ll mh = r[i].h;

			if (mh % ca == 0) tmp = mh / ca - 1;
			else tmp = mh / ca;

			ch -= ma * tmp;
			if (ch <= 0) return false;

		}
		else {
			ca += r[i].a;
			ch = min(m, ch + r[i].h);
		}
	}
	return true;
}

int main() {
	FASTIO;
	cin >> n >> h;

	r = vector<room>(n);
	for (int i = 0; i < n; i++)
		cin >> r[i].t >> r[i].a >> r[i].h;

	ll s = 1, e = 1e18, mid, ans = 0;

	while (s <= e) {
		mid = (s + e) / 2;

		bool isSuccess = simul(mid);
		if (isSuccess) {
			ans = mid;
			e = mid - 1;
		}
		else s = mid + 1;
	}

	cout << ans;
	return 0;
}

설명

매번 전투 시뮬레이션을 통해서  생명력을 구해나가면 됩니다. 이를 위해 이분탐색을 사용합니다.

 

느낀 점

이분탐색의 경우 처음에 최댓값을 뭐로 설정해야 할지 고민했는데, 이 부분을 제외하고는 괜찮았습니다!