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

문제 링크: https://www.acmicpc.net/problem/16434

16434번: 드래곤 앤 던전

1. 주의할 점

- 이분탐색을 사용한다

- 몬스터와 싸울 경우, While문을 통해 모든 과정을 반복하지 않는다-> While문 사용하면 TLE 발생

 

2. 구현

- Left = 1, Right = LLONG_MAX로 설정하며 이분탐색을 시작한다

- Cal(Mid) 함수를 통해 Mid의 체력으로 용사가 공주를 구할 수 있다면 True를, 구할 수 없다면 False를 반환하여 True라면 Right를 줄이고 False라면 Left를 줄인다

- Cal() 함수에서 용사가 몇번을 공격하면 몬스터가 죽는지 Mlife에 저장하고, 몬스터가 몇번 공격하면 용사가 죽는지 Wlife에 저장한다. 둘 모두 생명을 구할때, 적의 공격으로 인해 생명이 0으로 딱 떨어지지 않고 0 이하로 떨어지는 경우 생명을 1씩 더한다.

- 용사가 먼저 공격하므로, 몬스터의 수명이 용사의 수명보다 클 경우 False를, 아니라면 용사의 수명을 몬스터가 공격한 횟수만큼 깍고 계속 진행한다.

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;
long long result = 1, attack;
int num;
struct info {
	int t, a, h;
};
info arr[123457];

bool cal(long long mid) {
	long long tmp = mid;
	long long mtr_atk, mtr_hp, atk = attack;
	for (int i = 0; i < num; i++) {		
		if (arr[i].t == 1) {
			mtr_atk = arr[i].a;
			mtr_hp = arr[i].h;
			long long wlife = tmp / mtr_atk;
			if (tmp % mtr_atk != 0) wlife += 1;
			long long mlife = mtr_hp / atk;
			if (mtr_hp % atk != 0) mlife += 1;
			if (mlife > wlife) return false;
			tmp -= (mtr_atk*(mlife - 1));
		}
		else if (arr[i].t == 2) {
			atk += arr[i].a;
			tmp += arr[i].h;
			if (mid < tmp) tmp = mid;
		}
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> num >> attack;
	for (int i = 0; i < num; i++) {
		cin >> arr[i].t >> arr[i].a >> arr[i].h;
	}
	long long l = 1, r = LLONG_MAX, m;
	while (l <= r) {
		m = l + (r - l) / 2;
		if (cal(m)) {
			result = m;
			r = m - 1;
		}
		else
			l = m + 1;
	}
	cout << result;
	system("pause");
	return 0;
}