BOJ 16434 : 드래곤 앤 던전

풀이 요약

이분 탐색

풀이 상세

1. 이 문제에서 중요하게 바라볼 점은 2가지이다.

   • $MaxHP$ 를 구하는데 이분 탐색이 필요하다는 접근을 해야한다. 브루트 포스로 탐색하는 경우 시간 초과가 나올 것이다.
     최대 범위 : 용사의 공격력이 1이며, 123456 개의 스테이지가 존재하고 모든 스테이지는 몬스터방으로 구성되어 있고 모든 몬스터가 100만의 공격력을 가지고 있는 경우 ⇒ $1e6*1e6*123456$

   • 결투 진행 방식은 용사 선 공격, 몬스터 후 공격이다. 이 말은 용사가 몬스터를 죽이기까지 공격 횟수를 cnt 라 한다면 용사가 몬스터에게 공격 받는 횟수는 cnt-1 이 된다는 점을 인식해야한다.

2. 위의 내용을 기반으로 구현을 하면 된다. 단, 숫자 범위가 크니 long long 사용을 잊지말자.

의문점

• long long 할당 시 $1000000 * 1000000 * N$ 은 음수가 나오는데 $1e6*1e6*N$ 은 제대로 나온다. 뭐가 문제일까.

#include <iostream>
#define f first
#define s second
using namespace std;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef long long ll;
int N, A;
ll ans;
pii stage[123456 + 1];

bool go(ll hp) {
    ll currA = A;
    ll currHp = hp;
    for (int i = 0; i < N; i++) {
        if (stage[i].f == 1) {
            ll cnt = stage[i].s.s % currA == 0 ? stage[i].s.s / currA : stage[i].s.s / currA + 1;
            currHp -= (cnt - 1) * stage[i].s.f;
            if (currHp <= 0) return false;
        } else {
            currA += stage[i].s.f;
            currHp += stage[i].s.s;
            if (currHp > hp) currHp = hp;
        }
    }
    return true;
}

void solve() {
    ll l = 1;
    ll r = 1e6*1e6*N;
    while (l <= r) {
        ll mid = (l + r) / 2;
        if (go(mid)) {
            r = mid - 1;
            ans = mid;
        } else {
            l = mid + 1;
        }
    }
}

void input() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> A;
    int t, a, h;
    for (int i = 0; i < N; i++) {
        cin >> t >> a >> h;
        stage[i] = {t, {a, h}};
    }
}

void output() {
    cout << ans;
}

int main() {
    input();
    solve();
    output();
}