백준 16434번 드래곤 앤 던전 C++

문제

www.acmicpc.net/problem/16434

16434번: 드래곤 앤 던전

코드

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
ll n, attack, ret, t[123456], a[123456], h[123456];

bool check(ll mid)
{
    ll initHP = mid;
    ll initAttack = attack;

    for (int i = 0; i < n; i++)
    {
        if (t[i] == 2) //포션이 있는 방
        {
            mid = min(initHP, mid + h[i]);
            initAttack += a[i];
        }
        else //몬스터가 있는 방
        {
            ll forCeAttackCount = h[i] / initAttack + (h[i] % initAttack ? 1 : 0);
            ll monsterAttachCount = forCeAttackCount - 1;
            mid -= a[i] * monsterAttachCount;
        }

        if (mid <= 0)
            return false;
    }

    return true;
}

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

    cin >> n >> attack;
    for (int i = 0; i < n; i++)
    {
        cin >> t[i] >> a[i] >> h[i];
    }

    ll lo = 1, hi = 1e18, mid = 0, ret = 0;
    while (lo <= hi)
    {
        mid = (lo + hi) / 2;
        if (check(mid))
        {
            ret = mid;
            hi = mid - 1;
        }
        else
        {
            lo = mid + 1;
        }
    }

    cout << ret << "\n";

    return 0;
}