(2024-11-04) 1 문제 : 백준 - 16434 (드래곤 앤 던전)

 

문제 자체는 전형적인 이분탐색 문제이다. 최대 HP를 Mid로 잡고 해당 HP로 방을 몇개까지 클리어할 수 있는지를 확인하며 이분탐색을 수행하면 된다. 다만, 문제가 어렵다기보단 int형에서 오버플로우가 발생할 수 있으므로 long long 타입을 사용해야 문제가 틀리지 않는다. (본인도 몇 번 틀리다가 int를 싹다 long long으로 대체해봤더니 바로 맞는 것을 확인했다.)

#include <iostream>
#include <vector>
#include <climits>
#include <tuple>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

std::vector<std::tuple<long long, long long, long long>> RoomInfo;

long long GetMaxRoom(long long _MaxHp, long long _Atk)
{
    long long CurHp = _MaxHp;

    for (long long i = 0; i < RoomInfo.size(); i++)
    {
        auto [RoomType, Data_1, Data_2] = RoomInfo[i];

        if (RoomType == 1)
        {
            long long MonsterAtk = Data_1;
            long long MonsterHp = Data_2;

            long long PlayerAttackCount = MonsterHp / _Atk;
            if (MonsterHp % _Atk)
            {
                PlayerAttackCount++;
            }

            long long MonsterAttackCount = CurHp / MonsterAtk;
            if (CurHp % MonsterAtk)
            {
                MonsterAttackCount++;
            }

            if (MonsterAttackCount < PlayerAttackCount)
            {
                return i;
            }
            else
            {
                CurHp -= MonsterAtk * (PlayerAttackCount - 1);
            }
        }
        else
        {
            _Atk += Data_1;

            if (CurHp > LLONG_MAX - Data_2)
            {
                CurHp = LLONG_MAX;
            }
            else
            {
                CurHp = std::min(_MaxHp, CurHp + Data_2);
            }
        }
    }

    return RoomInfo.size();
}

int main()
{
    Init();

    long long NumRoom = 0, AtkPower = 0;
    std::cin >> NumRoom >> AtkPower;

    RoomInfo.resize(NumRoom);

    for (long long i = 0; i < NumRoom; i++)
    {
        std::cin >> std::get<0>(RoomInfo[i]) >> std::get<1>(RoomInfo[i]) >> std::get<2>(RoomInfo[i]);
    }

    long long Start = 0;
    long long End = LLONG_MAX;

    long long Answer = LLONG_MAX;

    while (Start <= End)
    {
        long long Mid = (Start + End) / 2;
        long long CurAnswer = GetMaxRoom(Mid, AtkPower);

        if (CurAnswer == RoomInfo.size())
        {
            Answer = std::min(Answer, Mid);
            End = Mid - 1;
        }
        else
        {
            Start = Mid + 1;
        }
    }

    std::cout << Answer;

    return 0;
}