16434번-드래곤앤던전

문제

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

16434번: 드래곤 앤 던전

---

접근방법

n의 단위가 100,000만 이므로 n^2의 알고리즘은 시간초과가 발생한다는것을 깨닫고 O(logn으로 시간복잡도를 줄여야 하는 문제란걸 문제의 조건을 읽고 알아야 하며 H의 범위가 1,000,000인데 최대 연산이 발생할 경우 INT의 범위를 초과하기에 자료형을 long long으로 설정해줘야 하는 문제이다.

 

문제를 읽고 탐색값을 "용사의 체력"으로 정해야지만 문제를 풀 수가 있다. 그렇기에 발생할 수 있는 범위를 정해주기 위해 left 값과 right값을 0과 LLONG_MAX의 범위로 설정해주었다. 그 이후 left와 right를 조절해주기 위해 check함수를 설정해주었다. 이 문제의 경우 "용사가 던전을 헤쳐나가는데 필요한 최소한의 체력"을 구하는 문제이기 때문에 이분 탐색중에 upper_bound형식의 이분탐색의 틀로 작성되어 있다. 그렇기에 마지막에 이분탐색이 종료되는 순간은 right가 정답이 되는 순간이다.이것은 이분탐색의 안의 특징을 이해해야한다. 어떤 문제가 주어질 때 최소한의 값을 찾는 경우를 가정할 때 while(left + 1 < rgiht)의 반복문 안에서 조건이 끝날 경우 x <=v[i - 1]의 값을 가져야 한다. (v는 입력의 배열) 그러기 위해서는 left의 값이 right의 자리에 도달할 경우 인데 이 순간이 조건이 끝나는 경우이므로 시작값은 right값에 남아있다. 이런 형식으로 코드를 작성하게 되면 자신이 작성한 코드의 논리가 upper_bound인지 lower_bound인지에 따라 Left값과 right값만 반화해주면 되므로 한 결 더 쉽고 생각한 문장을 그대로 옮기게 되는 코드를 작성할 수 있게된다.

---

정답코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
 
struct info{
    ll type;
    ll a;
    ll h;
 
    info(ll type, ll a, ll h) : type(type), a(a), h(h){}
};
 
const int MAX = 123456 + 1;
vector<info> arr;
int n, h;
 
bool check(ll mid, ll atackP)
{
    ll hp = mid;
    for (int i = 0; i < n; i++)
    {
        if (arr[i].type == 1)
        {
            ll cnt = arr[i].h / atackP;
            ll mod = arr[i].h % atackP;
            if (mod > 0)
                cnt++;
 
            //-1을 해주는 이유는 문제에서 주어지는 전투진행 순서를 자세히 봐야한다
            //용사가 먼저 공격하므로 몬스터가 죽으면 자신이 깍이는 피가 1번 없기 때문이다.
            ll monAtack = (cnt -1) * arr[i].a ;
            hp -= monAtack;
            if (hp <= 0)
                return false;
        }
        else if (arr[i].type == 2)
        {
            atackP += arr[i].a;
            hp = min(hp + arr[i].h, mid);
        }
    }
    return true;
}
 
int main(void)
{
    fastio;
    cin >> n >> h;
 
    for (int i = 0; i < n; i++)
    {
        int type, a, h;
        cin >> type >> a >> h;
        arr.push_back({ type, a, h });
    }
 
    ll left = 1;
    ll right = LLONG_MAX;
    ll ans;
    while (left + 1 < right)
    {
        ll atackP = h;
        ll mid = (left + right) / 2;
 
        if (!check(mid, atackP))
        {
            left = mid;
        }
        else
            right = mid ;
    }
 
    cout << right << "\n";
}