[Algorithm]Baekjoon 16434번 :: 드래곤 앤 던전

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
#include <mutex>
 
using namespace std;
 
struct Info
{
    long long t, a, h;
};
 
int n, h;
Info infos[123456];
long long answer = 0;
 
 
long long CanKill(long long heroDamage, long long heroHP, Info& monsterInfo) // 방 하나에서 죽일 수 있는지
{
    long long monsterAttackCount = (heroDamage + monsterInfo.h - 1) / heroDamage - 1;
 
    heroHP -= monsterInfo.a * monsterAttackCount;
 
    return heroHP <= 0 ? -1 : heroHP;
}
 
 
bool check(long long startHP)
{
    long long maxHP = startHP;
    long long curHP = maxHP;
    long long heroDamage = h;
 
    for (int i = 0; i < n; ++i)
    {
        Info& info = infos[i];
 
        if (info.t == 1) // 몬스터면,
        {
            curHP = CanKill(heroDamage, curHP, info);
 
            if (curHP != -1)
            {
                continue;
            }
            else
            {
                return false;
            }
        }
        else // 포션이면,
        {
            heroDamage += info.a;
            curHP = min(curHP + info.h, maxHP);
        }
    }
 
    return true;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> h;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> infos[i].t >> infos[i].a >> infos[i].h;
    }
 
    long long left = 1;
    long long right = LLONG_MAX-2;
 
 
    while (left <= right)
    {
        long long mid = (left + right) / 2;
  
        if (check(mid))
        {
            right = mid - 1;
            answer = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
 
    cout << answer;
}

 

 

문제에서 요구하는 출발시 최대HP값을 mid로 잡고 이분탐색하면서 해당값으로 던전을 클리어할 수 있는지 체크해주면 된다.

이 때, 한 층의 몬스터를 잡을 수 있는지 없는지를 체크하는 게 중요하다.

예를들어 영웅이 몬스터를 죽이기 위해 100번의 공격을 해야한다면, 그동안의 몬스터의 공격을 버틸 체력이 뒷받침해줘야 한다.

선공은 반드시 영웅이 가지고 있기 때문에 만약 영웅이 몬스터를 100번 공격해야 죽일 수 있다면, 영웅은 몬스터로부터 99번의 공격만 버틸 체력을 가지면 된다. 

 

long long monsterAttackCount = (heroDamage + monsterInfo.h - 1) / heroDamage - 1;

 

이게 몬스터가 플레이어를 공격하는 횟수가 된다. 

사실 정확히는 플레이어가 몬스터를 공격하는 횟수에서 1을 뺀거다.

플레이어가 몬스터를 공격하는 횟수를 정확히 구하려면 몬스터의 체력을 플레이어의 공격으로 나눈다음 올림을 해줘야 하는데,

그런 올림을 해주는 공식 중 하나가 (a + b - 1) / b 이다.

 

다만 STL의 ceil을 쓰면 더 간편하다.

 

long long monsterAttackCount = ceill((double)monsterInfo.h / heroDamage) - 1;