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

문제

난이도 : 골드 4
백준 16434번 : 드래곤 앤 던전

코드

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

ll N, atk;

struct Room
{
    int t, a, h;
};

vector<Room> v;

bool Check(ll maxHP)
{
    ll curHP = maxHP;
    ll curAtk = atk;

    for (int i = 0; i < N; i++)
    {
        int t = v[i].t;
        int a = v[i].a;
        int h = v[i].h;

        if (t == 1)
        {
            ll n = ceil((double)h / curAtk);

            if (curHP - a * (n - 1) <= 0) return false;
            curHP -= a * (n - 1);
        }
        else if (t == 2)
        {
            curHP = min(maxHP, curHP + h);
            curAtk += a;
        }
    }

    return true;
}
int main()
{
    cin >> N >> atk;

    for (int i = 0; i < N; i++)
    {
        Room room;
        cin >> room.t >> room.a >> room.h;
        
        v.push_back(room);
    }

    ll low = 0; ll high = LLONG_MAX;
    ll ret = LLONG_MAX;

    while (low <= high)
    {
        ll mid = (low + high) / 2;

        if (Check(mid))
        {
            high = mid - 1;
            ret = mid;
        }
        else
        {
            low = mid + 1;
        }
    }
    
    cout << ret << '\n';

    return 0;
}

풀이

이전까지의 이분 탐색 문제와 비슷하게 용사의 최대 피를 이분 탐색을 통해 최솟값을 찾는 문제이다.
Room 구조체를 만들어 방의 정보를 입력받고 벡터에 저장한다.
low와 high를 선언해 이 변수들로 이분 탐색을 할 것인데 이 때 변수의 범위를 잘 모르겠다면 사용하는 변수 타입의 MAX 값을 쓴다. 그런데 문제의 예제 2번에 보면 정답이 1000억이 넘는다. 이 말은? INT형을 못쓴다는 점. 그래서 나는 long long 타입으로 최솟값, 최댓값을 정했다.
이제 mid를 구해가며 Check 함수를 보자.
Check 함수의 처음엔 함수에서 쓸 현재 체력을 최대 체력으로 초기화하고 현재 공격력을 초깃값으로 초기화한다.
그리고 반복문을 통해 방을 돌아다니며 자기만의 로직을 구현하면 되는데 이 때 몬스터가 있는 방일때를 조심해야한다.
처음에 아무 생각 없이 while문으로 몬스터의 h가 0 이하일 때 까지로 했는데 그냥 틀렸다고 나와서 이거를 최적화 해줘야 한다.
용사가 몬스터를 잡을 수 있는 횟수는 바로 (몬스터의 피) / (용사의 공격력)인데 이게 0으로 떨어지면 잡는건데 0으로 안떨어지면 1번 더 공격해야 잡는거니까 통일성을 위해 ceil 함수로 올림 처리를 해주었다(이때 double형으로 타입변환 해줌)
그래서 구한 n번을 이용해 용사가 n번 때릴 때 몬스터는 용사를 n - 1번 때릴 수 있다. 왜냐면 용사가 먼저 공격이니까 먼저 공격해서 죽으면 몬스터는 공격을 못함
몬스터가 a라는 공격력으로 n - 1 번을 때렸을 때 만약 용사가 죽는다면? 바로 false를 리턴해 용사의 최대 체력을 올리는 로직을 실행함.
포션 방일때는 min(최대체력, 현재체력+포션)으로 min 값을 현재 체력에 덮어쓴다.
그리고 무사히 반복문을 빠져나가면 true를 리턴한다.

true를 리턴했으면 현재 구한 최대체력으로 던전이 돌아지는거니까 이거보다 더 작은 최대 체력으로도 돌아지는지 확인하면서 구하면 끝

결과