BOJ::16434 드래곤 앤 던전

[BOJ] : https://www.acmicpc.net/problem/16434

• Level : Gold 3

시사점

• 구현력과 이분탐색의 개념이 포함된 문제입니다.
• numeric_limits 로 unsinged long long 의 최대값을 추출하여 사용합니다.
• 주의할 점은 unsigned이므로 싸움 도중 용사의 체력을 깎을때,
  • 해당 감소분이 용사의 체력보다 큰지 비교하는 것입니다.
  • 무턱대고 용사의 체력 -= 감소분 진행 후 용사의 체력이 마이너스인지 확인하면 안 됩니다.

이해(10)

• 용사
  • 최대 체력
  • 현재 체력
  • 공격력
• 몬스터
  • 현재 체력
  • 공격력
• 포션
  • 공격력 추가분
  • 체력 추가분
• N개의 방이 존재하고 각 방에 몬스터 혹은 포션이 존재합니다.
• 몬스터가 존재하는 경우 돌아가면서 어택하며 싸워야 하고, 포션이 있는 경우 힐링을 진행합니다.
• 용사가 죽지 않고 N개의 방을 모두 순회할 수 있을정도의 체력을 구하는 문제입니다.

설계(11)

• 이분 탐색을 통해 조건을 만족하는 최소 체력을 찾습니다.
• 이때, 이분탐색의 범위를 구하는 것이 이 문제의 핵심이었다고 생각합니다.
• 최악의 경우, 용사의 공격력으로 1이 주어집니다.
  • 이때 N = 10^6 정도이고, 모든 방에 몬스터가 존재하고, 각 몬스터의 공격력은 10^6, 체력도 10^6입니다.
  • 포션이 없으므로 용사는 공격력 1로 모든 N마리의 몬스터를 물리쳐야 합니다.
  • 공격력 1로 몬스터를 쓰러트리기 위해서는 10^6번의 턴이 진행되어야 합니다.
    • 따라서 한 방마다 용사는 체력이 10^6(몬스터 공격력) * (10^6-1(몬스터 턴))씩 감소합니다.
    • 대략 10^12 정도입니다.
  • 따라서 총 방의 갯수 * 감소하는 체력을 구하면 10^18 입니다.
  • unsigned long long 이 대략 1.8 * 10^19 까지 커버하므로 충분합니다.
• 이후, 각 이분탐색마다 아래 과정을 진행하면 됩니다.
• 포션이 있는 방으로 간 경우 최대 체력이 초과되지 않는 점만 주의하면 됩니다.
• 몬스터가 있는 경우, 용사와 몬스터는 돌아가면서 1대씩 때리므로, 몬스터의 체력을 용사의 공격력으로 나누면 몇 번의 턴이 진행되는지 알 수 있습니다.

시간 복잡도

• 이분탐색으로 수를 구할때 end = unsigned long long 의 마지막 값 부근으로 10^19 정도 입니다.
• 따라서 O(logN)입니다.
  • 이후 정해진 mid마다 n개의 방을 통과할 수 있는지 확인합니다.
  • O(N)입니다.
• 물론 위의 각각의 N이 다르므로 O(N(10^6)) * O(logN(10^19)) 이 시간 복잡도가 됩니다.

공간 복잡도

구현(29)

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
struct cell{
    ull maxHP;
    ull curHP;
    ull attk;
};
struct input{ ull t; ull a;ull h; };
int n;
vector<input> rooms;
bool simulate(cell w){
    for(int i = 0; i < rooms.size(); i++){
        // fight
        if(rooms[i].t == 1){
            cell m = {rooms[i].h, rooms[i].h, rooms[i].a};
            ull w_attkCnt = (m.curHP/w.attk);
            if((m.curHP%w.attk) > 0) w_attkCnt += 1;
            if( (w_attkCnt-1) * m.attk  >= w.curHP ) return false;
            w.curHP -= (w_attkCnt-1) * m.attk;
        }
        // heal
        else{
            w.attk += rooms[i].a;
            w.curHP = min(w.maxHP, w.curHP + rooms[i].h);
        }
    }
    return true;
}
ull binarySearch(cell& w){
    ull ret = numeric_limits<unsigned long long>::max();
    ull begin = 1, mid = 0, end = numeric_limits<unsigned long long>::max() / 10;
    while(begin <= end){
        mid = (begin + end) /2;
        if(mid == 1){
            cout << "HERE" << endl;
        }
        w.maxHP = w.curHP = mid;
        if(simulate(w)){
            ret = min(ret, mid);
            end = mid -1;
        }else{
            begin = mid+1;
        }
    }
    return ret;
}
int main(){
    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cell w = {0, 0, 0};
    cin >> n >> w.attk;
    rooms = vector<input>(n, {0, 0, 0});
    for(int i = 0; i < n; i++)
        cin >> rooms[i].t >> rooms[i].a >> rooms[i].h;

    cout << binarySearch(w) << endl;
    return 0;
}

디버깅(x)

좋은 코드

• 수행속도가 빠른 대부분의 사람들은 이분 탐색 없이 답을 도출하였습니다.
• 아래는 백준에 공개 코드 처리해두신 isbidip님의 코드입니다.

• 매우 깔끔하게 정리되어 있어서 옮겨놓았습니다.

• 현재 체력과 최대 체력을 0으로 갖고 시뮬레이션을 진행합니다.
• 현제 체력이 0보다 작아지면,
  • 최대 체력 += (체력 감소분 - 현재 체력), 현재체력 = 0 을 만듦니다.
• 포션이 들어오면 현재체력을 일단 무조건 증가시킵니다.

• 이후, 현제체력은 mx값을 초과한 경우 mx로 변경하여 줍니다.

• 문제에 제시된 점을 그대로 구현하였지만, 한 가지 특이점은 용과 만나서 용의 총 공격 데미지가 현재 체력을 초과한 경우에 대한 처리라고 생각합니다.

• 이걸 어떻게 증명할 수 있을까요?
  • 전체 mx값을 도출한다기 보단, 각 방 마다 mx값을 갱신하는 것에 초점을 두면 좋을 것 같습니다.
  • 모든 방에 몬스터가 있다고 하면,
    • 계속해서 용사 체력의 마이너스 분 만큼 mx값이 커지게 됩니다.
    • 따라서 이 값 +1만 하면 용사는 해당 용에게 맞아 터져도 죽지 않을 만큼이 됩니다.
  • 만약 맞아터진 용사가 다음 방인 힐링을 만난다면, 최대 체력만큼 회복시켜 주면 됩니다.
    • 이때, 단순히 최대 체력만큼만 힐링을 해주는 것은 어차피 최대 체력은 맞을때마다 갱신되고, 용사 체력의 마이너스 분 만큼 반영되기 때문입니다.

#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    
    ll n,atk;cin>>n>>atk;
    ll curr=0, mx=0;
    while(n--){
        int t,a,h; cin>>t>>a>>h;
        if(t==1){
            ll damage=a*(ceil((double)h/atk)-1);
            if(damage>curr) mx+=damage-curr,curr=0;
            else curr-=damage;
        }else{
            atk+=a;
            curr+=h;
            if(curr>mx)curr=mx;
        }
    }
    cout<<mx+1;
}

최적화