[백준/BOJ] 백준 16434번 : 드래곤 앤 던전

www.acmicpc.net/problem/16434

16434번: 드래곤 앤 던전

이분 탐색을 이용해 문제를 해결했다. 해당 최대 생명력으로 해결이 가능한지 판단하는 것은 각 방을 돌며 다음 방으로 도달할 수 있는지 확인하는 것인데 몬스터를 만났을 때 용사와 몬스터가 이기기 위해 공격하는 횟수를 구해서 누가 이기는지 판단하였다. 그리고 오버플로우에 유의하였다. (예) (left / 2) + (right / 2); //더할때 오버플로우 방지로, 먼저 나눈 뒤 더했다)

 

코드

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

int n;
int first_attack;
vector<int> monster_attack(123456, 0);
vector<int> monster_hp(123456, 0);
vector<int> plus_attack(123456, 0);
vector<int> plus_hp(123456, 0);
vector<int> monster_potion(123456, 0);

bool Finish(long long max_hp, long long attack)
{
	long long hp = max_hp;

	for (int i = 0; i < n; i++)
	{
		if (monster_potion[i] == 1) //몬스터가 있을때
		{
			long long this_monster_hp = (long long)monster_hp[i];
			long long this_monster_attack = (long long)monster_attack[i];

			//용사가 몬스터를 이기기 위해 공격하는 횟수 구하기
			long long human_hit_cnt = this_monster_hp / attack; //용사가 몬스터 공격하는 횟수
			long long remain_monster_hp = this_monster_hp % attack;
			if (remain_monster_hp != 0)
				human_hit_cnt++;

			//몬스터가 용사를 이기기 위해 공격하는 횟수 구하기
			long long monster_hit_cnt = hp / this_monster_attack;
			long long remain_human_hp = hp % this_monster_attack;
			if (remain_human_hp != 0)
				monster_hit_cnt++;

			if (human_hit_cnt <= monster_hit_cnt) //용사가 이길때
			{
				hp -= (this_monster_attack * (human_hit_cnt - 1));
			}

			else //몬스터가 이길때
			{
				return false;
			}
		}

		else if (monster_potion[i] == 2) //포션이 있을때
		{
			//오버플로우일때
			if (hp + (long long)plus_hp[i] < 0)
				hp = max_hp;

			//최대 hp보다 커질때
			else if (hp + (long long)plus_hp[i] > max_hp)
				hp = max_hp;

			else
				hp += (long long)plus_hp[i];

			//오버플로우일때
			if (attack + (long long)plus_attack[i] < 0) 
				attack = numeric_limits<long long>::max();

			else
				attack += (long long)plus_attack[i];
		}
	}

	return true;
}

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


	cin >> n >> first_attack;

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

		if (t == 1)
		{
			monster_potion[i] = 1;

			monster_attack[i] = a;
			monster_hp[i] = h;
		}

		else if (t == 2)
		{
			monster_potion[i] = 2;

			plus_attack[i] = a;
			plus_hp[i] = h;
		}
	}

	long long left = 1;
	long long right = numeric_limits<long long>::max();
	long long result;

	//이분 탐색을 이용한다
	while (left <= right)
	{
		long long mid = (left / 2) + (right / 2); //더할때 오버플로우 방지로, 먼저 나눈뒤 더한다

		if (Finish(mid, first_attack) == true)
		{
			result = mid;
			right = mid - 1;
		}

		else
		{
			left = mid + 1;
		}
	}

	cout << result;

	return 0;
}