문제

문제 링크

해설

• 방의 개수(N)와 몬스터의 체력(h)의 범위가 커서 최악의 경우에는 시간초과가 날 수 있는 구현문제입니다.
• 각 방에서 해야하는 일이 순서대로 정리돼있기 때문에 문제에 나와있는대로 구현만 하면 됩니다.
• 하지만, 시간초과를 방지하기 위해 for문으로 정직하게 한 턴씩 몬스터와 때리고 맞고를 주고받을 필요가 없습니다. 나누기 연산으로 몬스터를 죽이기 위해 필요한 턴 횟수를 한 번에 계산한 뒤, 죽지않기 위해 필요한 최소한의 체력을 O(1)에 계산하면 됩니다.
  • 몬스터와의 공방 과정에서 주인공은 몬스터에게 데미지를 입습니다.
  • 주인공이 몬스터에게 선빵을 치기 때문에, 주인공이 입는 데미지는 몬스터 공격력 × (ceil(몬스터체력 ÷ 현재공격력) - 1)으로 계산할 수 있습니다.
  • 만일 현재체력(HcurHP)이 이 데미지보다 크다면, 그냥 데미지를 입으면 됩니다.
  • 만일 현재체력(HcurHP)이 이 데미지보다 작다면, 최대체력(HmaxHP)를 위 데미지를 입고 살 수 있을 만큼만 늘려주면 됩니다.
• 포션이 있는 방에서는 현재체력이 최대체력을 넘지 못하도록 HcurHP = min(HcurHP + h, HmaxHP)로 계산합니다.

코드

#include <bits/stdc++.h>
using namespace std;

long long N, Hatk, HcurHP, HmaxHP, dmg;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> Hatk;
	
    for (int i = 0; i < N; ++i) {
		int t, a, h;
		cin >> t >> a >> h;
		
        if (t == 1) {   // monster
			dmg = (ceil((double)h / Hatk) - 1) * a;
			
            if (HcurHP >= dmg) HcurHP -= dmg;
			else {      // Increase max HP if monster not dead.
				HmaxHP += dmg - HcurHP;
				HcurHP = 0;
			}
		} else {        // potion
			Hatk += a;
			HcurHP = min(HcurHP + h, HmaxHP);
		}
	}
	cout << HmaxHP + 1;
}

소스코드 링크

결과!