백준 16434번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	256MB	골드 4

사진을 클릭하면 문제로 이동합니다.

---

풀이

 솔직히 이분탐색을 생각하긴 했지만, 안써도 풀릴 것 같아 일부러 쓰지 않고 풀어본 문제이다. 이분탐색을 쓰면 어떠한 MaxHp를 고른 다음에, 그 MaxHp로 던전을 클리어할 수 있는지 확인하면 될테니 말이다. 하지만, 처음에 이분탐색을 생각하지 않고 구상중이던 풀이가 있기 때문에 그 풀이로 계속 풀어보았다.

 

 MaxHp라고 계속 쓰기 좀 귀찮으니까 m이라고 하자. 현재 체력을 c라고 하자. 문제의 조건에 따라 맨 처음에는 c = m이다. 던전의 스테이지를 지나갈수록 c는 점점 낮아질 것이다. 우리의 목표는 이 c가 0이 되지 않도록 하는 것이다. 예제 입력 1을 통해 더 구체화해보자. 예제 입력 1은 다음과 같다.

 

3 3
1 1 20
2 3 10
1 3 100

 

우리는 모든 구간에서 c가 1 이상이어야 한다. 첫번째 방에서는 6번의 피격이 일어나고, 그때 몬스터의 공격력은 1이기 때문에 총 6만큼의 체력이 줄어든다. 이때의 c는 m - 6일 것이다. 두번째 방에서 체력을 10 회복한다. 하지만 우리는 6만큼 체력이 깎인 상태이고, 현재 체력은 최대 체력을 초과할 수 없기 때문에, 두번째 방에서 우리의 체력은 m이 된다. 다음 세번째 방에서는 16번의 피격이 일어날 것이다. 공격력이 6으로 증가했기 때문이다. 이때의 몬스터의 공격력은 3이기 때문에 우리의 체력은 m - 48이 될 것이다. 여기서 얻을 수 있는 세개의 부등식을 모두 만족해야 한다.

 

m > 0, m > 6, m > 48

 

이 모두를 만족하는 m값은 49이다. 그리고 이것이 답이다. 조금 일반화를 해보면, 다음과 같은 부등식들을 찾았다고 하자.

 

m > a1, m > a2 , m > a3, ... , m > ak

 

a1...ak 중에서 제일 큰 값을 a_max라고 해보자. 그렇다면 모든 부등식을 만족하는 m의 최솟값은 1 + a_max일 것이다. 이를 코드에 적용하면 된다.

 

또한, 피격 횟수에 유의해야한다. 몬스터와의 전투를 치를때에는 턴제게임마냥 플레이어가 먼저 때린 후, 그다음 몬스터가 생존해있다면 피격당한다. 공격력이 2이고, 몬스터의 체력이 4라면, 4 -> 2 -> 0이기 때문에 한번의 피격이 일어난다. 하지만 몬스터의 체력이 3이어도 3 -> 1 -> 0으로 한번의 피격이 일어난다. 몬스터의 체력이 플레이어의 공격력의 배수라면 플레이어의 공격력으로 나눈 몫에서 1을 더 빼줘야 하고, 그렇지 않다면 그냥 몫 값이 피격 횟수이다.

코드

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

ll n, atk;
vector<tuple<ll,ll,ll>> dungeon;


void input() {
	cin >> n >> atk;
	dungeon.resize(n);
	for(auto& [t, a, h] : dungeon) cin >> t >> a >> h;
}

void sol() {
	ll ans = 0LL, cur_hp = 0LL;

	for(auto& [t, a, h] : dungeon) {
		if (t == 1) {
			cur_hp -= a * (h / atk - (h % atk ? 0 : 1));
		}
		else {
			atk += a;
			cur_hp = min(0LL, cur_hp + h);
		}
		ans = min(ans, cur_hp);
	}

	cout << 1 - ans;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	input();
	sol();
}