[ BOJ 백준 16434번 - 드래곤 앤 던전 ] 해설 및 코드

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

 

목적

던전의 모든 용을 쓰러뜨리기 위한 용사의 최대 체력을 구하자.

 

접근법

1. 이분 탐색으로 푼 사람들도 많지만, 이 문제는 구현문제다. 그냥 O(n)의 시간복잡도로 풀자.

 

#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    
    ll n,atk;cin>>n>>atk;
    ll curr=0, mx=0;
    while(n--){
        int t,a,h; cin>>t>>a>>h;
        if(t==1){
            ll damage=a*(ceil((double)h/atk)-1);
            if(damage>curr) mx+=damage-curr,curr=0;
            else curr-=damage;
        }else{
            atk+=a;
            curr+=h;
            if(curr>mx)curr=mx;
        }
    }
    cout<<mx+1;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.