[백준] 16434 드래곤 앤 던전💫

[백준] 16434 드래곤 앤 던전

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

틀린 풀이

• 맞왜틀

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

typedef long long ll;
 
//방의 개수
ll N;
//용사의 공격력
ll ATK;

//방 정보
//t = 1 -> 공격력 a, 생명력 h인 몬스터
//t = 2 -> 공격력 a, 생명력 h 증가 포션
vector<vector<ll>> room;

//용사의 최대 생명력 x일 때 N번째 방까지 갈 수 있는가
bool decision(ll x) {
	ll curHP = x;
	ll curATK = ATK;

	for (int i = 0; i < N; ++i) {
		ll t = room[i][0]; 
		ll a = room[i][1]; 
		ll h = room[i][2];
		//몬스터 방
		if (t == 1) {
			ll mATK = a;
			ll mHP = h;

			while (true) {
				mHP -= curATK;
				if (mHP <= 0) {
					break;
				}
				curHP -= mATK;
				if (curHP <= 0) {
					return false;
				}
			}
		}
		//포션 방
		else {
			curATK += a;
			curHP = min(x, curHP + h);
		}
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> ATK;
	for (int i = 0; i < N; ++i) {
		ll t, a, h;
		cin >> t >> a >> h;

		vector<ll> v;
		v.push_back(t);
		v.push_back(a);
		v.push_back(h);
		room.push_back(v);
	}

	ll lo = 1;
	ll hi = LLONG_MAX;
	while (lo + 1 < hi) {
		ll mid = (lo + hi) / 2;
		if (decision(mid)) hi = mid;
		else lo = mid;
	}

	cout << hi;
	return 0;
}