[백준 16434번] [이분 탐색] 드래곤 앤 던전

처음에는 MAX값을 변수로 두고, 최종 결과까지 가면서 남아있는 체력이 0 초과하기 위한 범위를 구하고

이 중 최솟값을 출력하는 방식으로 구현하려고 하였다.

 

사실 구현 양상을 보면 충분히 가능해보인다.

 

다만, 다른 방법으로는 가장 최악의 경우 몬스터가 엄청 쎄고 용사는 매우 약하다고 가정해보면

123456개의 방에서 몬스터의 공격력은 1000000이고, 체력도 1000000인데 용사의 공격력은 1이라고 하면

이 경우 최대 hp는 이 3개의 값을 곱한 값이다.

 

즉, HP는 1과 위의 최대 hp 사이에 존재할 수 밖에 없는 것을 활용해서 직접 다 계산해주면 된다.

최대 HP를 k라 하면 시간 복잡도는 O(nlgk)이므로 충분히 시간안에 돌아간다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef long long ll;

int main(void){
    fastio;
    ll n, atk;
    cin >> n >> atk;
    vector<vector<ll> > data_set(n);

    for(int i = 0; i < n; i++){
        ll temp1, temp2, temp3;
        cin >> temp1 >> temp2 >> temp3;
        data_set[i].push_back(temp1);
        data_set[i].push_back(temp2);
        data_set[i].push_back(temp3);
    }
    ll start = 1;
    ll end = 2e17;

    while(start < end){
        ll mid = (start + end) / 2;
        ll current_hp = mid;
        ll current_atk = atk;
        bool check = true;
        for(int i = 0; i < n; i++){
            // 공격 타이밍
            if(data_set[i][0] == 1){
                if(data_set[i][2] % current_atk == 0){
                    current_hp -= ((data_set[i][2] / current_atk) - 1) * data_set[i][1];
                }
                else current_hp -= (data_set[i][2] / current_atk) * data_set[i][1];
                // 뒤진 상황
                if(current_hp <= 0){
                    start = mid + 1;
                    check = false;
                    break;
                }
            }
            else{
                current_hp = min(mid, current_hp + data_set[i][2]);
                current_atk += data_set[i][1];
            }
        }
        // 살아남은 경우
        if(check){
            end = mid;
        }
        else{
            start = mid + 1;

        }
    }

    cout << start << "\n";
    return 0;
}