백준 16434번 드래곤 앤 던전 ( C++ )

문제

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

 

해설

stack에 담고 뒤에서 부터 풀면 쉽게 풀 수 있음

 

코드

#include<iostream>
#include<algorithm>
#include<stack>
 
using namespace std;
typedef long long ll;
ll room_num, str, hp,room_type,room_str,room_hp,attack_cnt,max_hp;
stack<tuple<int,int,int>> s;
 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);cout.tie(NULL);
 
  cin >> room_num >> str;
 
  for(int i=0;i<room_num;i++){
    cin >> room_type >> room_str >> room_hp;
    if(room_type == 2){
      str += room_str;
    }
    s.push({room_type,room_str,room_hp});
  }
 
  hp = 1;
  for(int i=0;i<room_num;i++){
    tie(room_type,room_str,room_hp) = s.top();
    s.pop();
    if(room_type == 1){ 
      attack_cnt = room_hp/str;
      if(room_hp%str == 0) attack_cnt--;
 
      hp += attack_cnt*room_str;
    }
 
    else{
      str -= room_str;
      hp -= room_hp;
      if(hp<=0){
        hp = 1;
      }
    }
    max_hp = max(hp,max_hp);
  }
 
  cout << max_hp;
  return 0;
}