[백준][C++] 16434 드래곤 앤 던전

www.acmicpc.net/problem/16434

16434번: 드래곤 앤 던전

 

 

 

알고리즘 종류

구현

 

 

사고 과정

던전을 지나 N번 방에 몬스터를 쓰러트리고 아름다운 공주를 구하기 위한 최소 MaxHP를 구하는 문제이다. 간단하게 이분탐색을 이용해서 해결할 수 있다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
 
using namespace std;
 
long long n, atk;
long long ans;
 
vector<pair<int, pair<long long, long long> > > dungeon;
 
 
bool go(long long hp){
    
    long long ca = atk;
    long long ch = hp;
    
    for(int i=0; i<n; i++){
        
        int state = dungeon[i].first;
        
        // monster
        if(state == 1){
            long long ma = dungeon[i].second.first;
            long long mh = dungeon[i].second.second;
            
            long long t;
            if(mh % ca == 0) t = mh/ca - 1;
            else t = mh/ca;
            
            ch -= ma * t;
            if(ch <= 0) return false;
        }
        // portion
        else{
            ca += dungeon[i].second.first;
            ch = min(hp, ch + dungeon[i].second.second);
        }
    }
    return true;
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> atk;
    
    int a, b, c;
    for(int i=0; i<n; i++){
        cin >> a >> b >> c;
        dungeon.push_back({a, {b, c}});
    }
    
    long long left = 1;
    long long right = 1e18;
    long long mid;
    
    while(left <= right){
        mid = (left + right)/2;
        
        if(go(mid)){
            right = mid - 1;
            ans = mid;
        }
        else{
            left = mid + 1;
        }
    }
    
    cout << ans << endl;
}

 

 

 

시행착오