[c++] 백준 16434 드래곤 앤 던전 (이분 탐색 / binary search)

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

Binary Search / 이분탐색

오름차순의 값 left ~ right 사이의 중간위치 mid를 구하여 array[mid]의 값과 타겟을 비교한다.
-> 타겟이 mid의 값보다 작다면 : right = mid
-> 타겟이 mid의 값보다 크다면 : left = mid + 1;
시간복잡도 O(logN)

이분탐색인 이유

입력 조건 : 방의 개수 N (1 ≤ N ≤ 123,456)
HMaxHP 의 값을 1부터 최대값까지 계산하면 시간초과가 난다.

left, right 값 설정하는 과정에서 HMaxHP의 최댓값이 아주 크다는 사실을 알게되었다.
left를 1로, right를 1e12 로 설정해주었더니 right의 값이 부족해서 틀렸습니다를 겪었다.
right값을 9e18 로 설정하여 여유있게 통과할 수 있었다.

10억이상이면 이분탐색을 쓰라는 글을 본 적이 있었던 것 같기도..

tuple

방의 상태, 몬스터의 공격력, 몬스터의 생명력 을 저장하는 tuple을 가진 vector배열을 사용했다.

typedef tuple<int, int, int> t;
vector<t> v;

check 함수

해당 hp로 용사의 생존 가능을 검사하는 함수

bool check(long long HP) {
    long long atk = m, hp = HP; // 공격력, 생명력

    for (int i = 0; i < n; i++) {
        int state, ma, mh; // 방의 상태, 몬스터의 공격력, 몬스터의 생명력
        tie(state, ma, mh) = v[i];

        if (state == 1) { // 몬스터
            long long t; // 쓰러트리기까지의 횟수
            if (mh % atk == 0)
                t = mh / atk - 1;
            else
                t = mh / atk;
            hp -= ma * t;
            
            if (hp <= 0) return false; // 생존 불가능
        } else { // 포션
            atk += ma; // 공격력 증가
            hp = min(HP, hp + mh); // 생명력 회복
        }
    }

    return true; 
}

전체코드

#include <algorithm>
#include <iostream>

using namespace std;

typedef tuple<int, int, int> t;

int n, m;
vector<t> v;
long long res;

bool check(long long HP) {
    long long atk = m, hp = HP;

    for (int i = 0; i < n; i++) {
        int state, ma, mh;
        tie(state, ma, mh) = v[i];

        if (state == 1) {
            long long t;

            if (mh % atk == 0)
                t = mh / atk - 1;
            else
                t = mh / atk;

            hp -= ma * t;
            if (hp <= 0) return false;
        } else {
            atk += ma;
            hp = min(HP, hp + mh);
        }
    }

    return true;
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v.push_back({a, b, c});
    }

    long long left = 1, right = 1e18;
    while (left <= right) {
        long long mid = (left + right) / 2;

        if (check(mid)) {
            right = mid - 1;
            res = mid;
        } else {
            left = mid + 1;
        }
    }
    cout << res;

    return 0;
}