드래곤 앤 던전

분석

던전 탐험하면서 최소의 MaxHp로 공주를 구하는 문제이다.

예시를 보면알지만 범위가 크기 때문에 long long사용해야한다.

용사 공격력 1이고 용체력 100만, 공격력 100만, 던전 10만개일경우

최대범위가 10만 100만 100만이다.

후기

로직은 맞았는데 한40%쯤에서 계속 시간 초과가 떳었는데 이전에 작성한 체력을 깍고 깍는 부분에서

while (1)
{
	a._monsterHpOrinHp -= curDamage;
	if (a._monsterHpOrinHp <= 0) break;

	curHp -= a._damageOrInAttack;
	if (curHp <= 0) return false;
}

while을 돌리다보니까 만약 공격력이 1이고 포션이 하나도 없는 경우때문에 이런일이 발생한거같다.

그래서 서로 때리는 로직을 이렇게 구현하는게 아니라

그냥 mod 연산자와 나누기로 총 공격횟수를 구해버리는 것이다.

용사가 만약 3번공격해서 몬스터가 죽는경우 몬스터는 무조건 2번은 공격한다.

그러면 몬스터가 플레이러를 두번공격하는 동안 플레이어의 체력이 남아있는지 아닌지를 보면 되는것이다.

cpp코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define ll long long
#define endl "\n"

int roomCnt, damage;
ll ret = 1e19;

struct Info
{
	int _infoNum;
	int _damageOrInAttack;
	int _monsterHpOrinHp;
};

queue<Info> q;
vector<Info> vec;
pair<ll, ll> player;

bool Check(ll hp, int playerDamage)
{
	ll maxHp = hp;
	ll curHp = hp;
	ll maxDamage = 1000000;
	ll curDamage = playerDamage;

	for (int i = 0; i < vec.size(); ++i)
	{
		Info a = vec[i];
		if (a._infoNum == 1)
		{
			ll playerAttackCnt = a._monsterHpOrinHp / curDamage + (a._monsterHpOrinHp % curDamage ? 1 : 0);

			ll monsterAttackCnt = playerAttackCnt - 1;

			curHp -= (monsterAttackCnt * a._damageOrInAttack);
			if (curHp <= 0) return false;
		}
		// 포션
		else
		{
			curHp += a._monsterHpOrinHp;
			if (curHp > maxHp) curHp = maxHp;
			curDamage += a._damageOrInAttack;
			if (curDamage > maxDamage) curDamage = maxDamage;
		}

	}
	return true;
}

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

	cin >> roomCnt >> damage;
	int v0, v1, v2;
	for (int i = 0; i < roomCnt; ++i)
	{
		cin >> v0 >> v1 >> v2;
		vec.push_back({v0, v1, v2});
	}

	ll lo = 1, hi = 1e18;
	while (lo <= hi)
	{
		ll mid = (lo + hi) / 2;
		if (Check(mid, damage))
		{
			hi = mid - 1; ret = mid;
		}
		else lo = mid + 1;
	}
	
	cout << ret << endl;
	return 0;
}