[백준] 16434 드래곤 앤 던전

이 문제는 이분탐색 or 시물레이션으로 풀 수있는것같다

주구장창 시물레이션 풀다가 계속 틀렸다

최적화의 계산을 정~~~~말 못해서 그런거같다

 

이분탐색도 생각 못했다.. 최소의 최대체력인데..!!! 문제에 써있는데..!!

최대체력을 mid로 두고 이분탐색을 해서 그 체력이 가능한지 돌려보자!

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long
ll n,k;
vector<pair<ll,pair<ll,ll>>> vt;
 
bool solve(ll mid){
    ll atk =k;
    ll hp = mid;
    for(int i=0;i<n;i++){
        if(vt[i].first==1){
            ll cnt = vt[i].second.second/atk;
            if(vt[i].second.second%atk) cnt++;
            cnt--;
            hp-=(cnt*vt[i].second.first);
            if(hp<=0) return false;
        } else {
            atk+=vt[i].second.first;
            hp+=vt[i].second.second;
            if(hp>mid) hp=mid;
        }
    }
    return true;
}
int main(){
    //freopen("input.txt","r",stdin);
    scanf(" %lld %lld",&n,&k);
    for(int i=0;i<n;i++){
        ll a,b,c; scanf(" %lld %lld %lld",&a,&b,&c);
        vt.push_back({a,{b,c}});
    }
    ll l=1,r=1e18,ans=1e18;
    while(l<=r){
        ll mid = (l+r)/2;
        if(solve(mid)){
            ans = min(ans,mid);
            r = mid-1;
        } else l = mid+1;
    }
    printf("%lld\n",ans);
}