BOJ 16434 - 드래곤 앤 던전 링크
(2023.09.15 기준 G4)

문제

N개의 방으로 이루어진 던전이 있고, 용사는 초기 공격력 ATK를 가지고 있다.
모든 방은 차례대로 방문해야 하며, N번째 방에는 공주와 용이 있으며 용을 무찌르면 공주를 구할 수 있다.

몬스터가 있는 방에는 다음과 같이 전투가 진행된다.

1. 용사의 공격력 HATK만큼 몬스터의 생명력을 깎습니다.
2. 몬스터의 생명력이 0 이하이면 전투가 종료되고 용사는 다음 방으로 이동합니다.
3. 몬스터의 공격력만큼 용사의 생명력 HCurHP를 깎습니다.
4. 용사의 생명력이 0 이하이면 전투가 종료되고 용사는 사망합니다.
5. 다시 1부터 진행합니다.

포션에 있는 방에 도착하면 공격력이 일정량 증가하며, 생명력도 최대 생명력을 넘지 않게 일정량 회복된다.

공주를 구하기 위한 최소한의 최대 생명력 출력

알고리즘

시뮬레이션을 곁들인 이분 탐색

풀이

최대 생명력이 높을수록 공주를 구했을 때 남는 생명력이 많아진다. 이는 자명하다.
이는 단조증가 함수이므로 이분 탐색을 사용 가능하다.

최대 생명력을 이분 탐색으로 조절하면서, 문제 지문 그대로 시뮬레이션을 돌려서 공주를 구하게 되면 조절한 최대 생명력이 가능함을 알 수 있게 된다.

물론, 몬스터가 있는 방에서의 전투 시뮬레이션에서는, 한방한방 주고받지 말고, 용사가 때려야 하는 최소 횟수, 몬스터가 때려야 하는 최소 횟수를 구하는 식으로 진행하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef tuple<int, int, int> tiii;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, ATK; cin >> N >> ATK;
    tiii stages[N];
    for (int i = 0; i < N; i++) cin >> get<0>(stages[i]) >> get<1>(stages[i]) >> get<2>(stages[i]);

    // 용사의 공격력은 1이고
    // 123,456개의 방에, 체력과 공격력이 1,000,000인 몬스터가 있을 때의 살 수 있는 HP를 최대로 잡아야 한다.
    // 123,456 × 999,999 × 1,000,000 + 1 = 123,455,876,544,000,001
    ll st = 1, en = 123455876544000001;
    while (st < en){
        ll MH = (st + en) >> 1, H = MH; // 최대 체력, 현재 체력
        ll A = ATK; // 현재 공격력

        // 시뮬레이션 시작
        bool win = true;
        for (auto [t, a, h]: stages){

            // 몬스터가 있다면 싸운다.
            if (t == 1){
                ll hit_hero = ceil((double)h / A); // 용사가 때려야 하는 횟수
                ll hit_monster = ceil((double)H / a); //  몬스터가 때려야 하는 횟수
                if (hit_hero <= hit_monster) // 용사가 때려야 하는 횟수가 더 적거나 같으면 용사가 이긴다.
                    H -= (hit_hero - 1) * a; // (용사가 때리는 횟수 - 1)만큼 몬스터한테 맞는다.
                else{ // 졌다면 시뮬레이션 종료
                    win = false;
                    break;
                }
            }

            // 포션이 있다면 마신다.
            else{
                A += a;
                H = min(MH, H + h);
            }
        }

        // 이겼다면 현재 체력은 가능한 체력이다.
        if (win) en = MH;
        else st = MH + 1;
    }

    cout << st;
}

• Python

import sys; input = sys.stdin.readline
from math import ceil

N, ATK = map(int, input().split())
stages = [tuple(map(int, input().split())) for _ in range(N)]

# 용사의 공격력은 1이고
# 123,456개의 방에, 체력과 공격력이 1,000,000인 몬스터가 있을 때의 살 수 있는 HP를 최대로 잡아야 한다.
# 123,456 × 999,999 × 1,000,000 + 1 = 123,455,876,544,000,001
st = 1; en = 123455876544000001
while st < en:
    MH = H = (st + en) >> 1 # 최대 체력, 현재 체력
    A = ATK # 현재 공격력

    # 시뮬레이션 시작
    win = True
    for t, a, h in stages:

        # 몬스터가 있다면 싸운다.
        if t == 1:
            hit_hero = ceil(h / A) # 용사가 때려야 하는 횟수
            hit_monster = ceil(H / a) # 몬스터가 때려야 하는 횟수
            if hit_hero <= hit_monster: # 용사가 때려야 하는 횟수가 더 적거나 같으면 용사가 이긴다.
                H -= (hit_hero - 1) * a # (용사가 때리는 횟수 - 1)만큼 몬스터한테 맞는다.
            else: # 졌다면 시뮬레이션 종료
                win = False
                break

        # 포션이 있다면 마신다.
        else:
            A += a
            H = min(MH, H + h)

    # 이겼다면 현재 체력은 가능한 체력이다.
    if win:
        en = MH
    else:
        st = MH + 1

print(st)