백준 16434번 : 드래곤 앤 던전 - 이분탐색, 구현 C++

https://www.acmicpc.net/problem/16434

16434번: 드래곤 앤 던전

1. 문제설명

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

이 순서를 잘 고려하여 몬스터와 용사의 싸움을 잘 구현해야 문제를 해결 할 수 있다.

몬스터가 먼저 죽으면 몬스터는 용사에게 공격할 수 없다!

 

 

 

---

 

 

2. 문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;


int N, H_atk;
int room[123457][3];

void Input() {
    cin >> N >> H_atk;

    for (int i = 0; i < N; i++) {
        cin >> room[i][0] >> room[i][1] >> room[i][2];
    }
}

bool play(ll hp, int attack) {
    ll curHp = hp;
    ll curAttack = attack;

    for (int i = 0; i < N; i++) {
        if (room[i][0] == 1) {
            
            ll turnToMonsterDie = (room[i][2] / curAttack) + (room[i][2] % curAttack > 0 ? 1 : 0);
            ll turnToKnightDie = (curHp / room[i][1]) + (curHp % room[i][1] > 0 ? 1 : 0);

            if (turnToMonsterDie > turnToKnightDie) {
                return false;
            } else {
                curHp -= room[i][1] * (turnToMonsterDie -1);
            }

        } else {
            curHp += room[i][2];
            if (curHp > hp) curHp = hp;

            curAttack += room[i][1];
        }
    }

    return true;
}


ll binarySearch() {
    ll st = 1, en = 9e18;

    while (st <= en) {
        ll mid = st + (en - st) / 2;

        if (play(mid, H_atk)) {
            en = mid - 1;
        } else {
            st = mid + 1;
        }
    }

    return st;
}


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

    Input();
    cout << binarySearch() << '\n';

    return 0;
}