[백준 30701] 돌아온 똥게임 (C++)

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

문제

---

유튜브에서 똥게임 광고를 지나치게 많이 본 근호는 본인이 직접 똥게임을 설치해서 하기로 했다.

처음에 근호는 D의 전투력을 가지고 시작한다. 근호 앞에는 N개의 방이 있는데, 각 방에는 몬스터 또는 장비가 있으며 i(1 ≤ i ≤ N)번째 방에 있는 몬스터 또는 장비는 전투력 X_i를 가진다.

근호는 매번 아직 돌파하지 않은 방 중 어떤 방에 먼저 들어갈지 자유롭게 정할 수 있으며, 들어간 방에 있는 내용물에 따라 다음과 같이 행동한다.

• 몬스터가 있는 경우: 근호의 전투력이 몬스터의 전투력보다 크면 몬스터를 쓰러뜨릴 수 있으며, 이후 근호의 전투력에 몬스터의 전투력이 더해진다. 근호의 전투력이 몬스터의 전투력보다 작거나 같을 경우 근호는 패배한다.
• 장비가 있는 경우: 근호의 현재 전투력에 상관없이 얻을 수 있으며, 근호의 전투력에 장비의 전투력이 곱해진다. 단, 현재 얻고자 하는 장비보다 전투력이 작은 모든 장비를 얻어야만 현 장비를 얻을 수 있다.

방에 있는 몬스터를 쓰러뜨리거나 장비를 얻을 경우 해당 방을 돌파한 것이며, 근호가 모든 방을 돌파하거나 몬스터에게 패배했을 경우 게임이 끝난다.

근호가 최선의 전략으로 게임을 진행할 때, 최대로 돌파할 수 있는 방의 수를 구하여라.

근호가 게임 중 행동을 통해 올릴 수 있는 전투력에 상한이 없음에 유의하자.

입력

---

첫 번째 줄에는 방의 수 N과 근호의 시작 전투력 D가 공백으로 구분되어 정수로 주어진다. (1 ≤ N ≤ 100000; 1 ≤ D ≤ 10⁹)

다음 N개 줄에는 한 줄에 하나씩 방의 정보 A_i,X_i가 공백으로 구분되어 정수로 주어진다. A_i는 1또는 2이며, 1이면 몬스터가 있는 방이고 2이면 장비가 있는 방이다. X_i (2 ≤ X_i ≤ 10⁹)는 해당 방에 있는 몬스터 또는 장비가 가진 전투력이다.

출력

---

첫 번째 줄에 근호가 최대로 돌파할 수 있는 방의 수를 출력한다.

 

문제 풀이

---

그리디 문제.

 

장비는 곱셈 연산이므로 근호의 전투력이 클수록 이득을 본다. 따라서 몬스터를 쓰러뜨릴 수 없을 때까지 몬스터를 쓰러뜨리고, 다음에 대결해야 할 몬스터가 쓰러뜨릴 수 없다면 장비를 얻어 강해진 후 둘 사이의 전투력을 비교한다. 몬스터를 모두 쓰러뜨린 상태라면 순서에 상관없이 아무 장비나 획득함으로써 방을 돌파해주면 된다.

몬스터와 장비를 각각 나누어 작은 순서대로 우선순위 큐에 저장하여 구현하면 된다.

 

아래는 코드.

#include <iostream>
#include <queue>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	long long D, N;
	long long A, X;
	long long answer = 0;
	cin >> N >> D;
	priority_queue<long long, vector<long long>, greater<>> monster;
	priority_queue<long long, vector<long long>, greater<>> eqip;
	for (int i = 0; i < N; i++)
	{
		cin >> A >> X;
		if (A == 1)
		{
			monster.push(X);
		}
		else
		{
			eqip.push(X);
		}
	}
	while (!monster.empty() || !eqip.empty())
	{
		if (!monster.empty())
		{
			long long top = monster.top();
			if (D <= top)
			{
				if (eqip.empty())
				{
					break;
				}
				else
				{
					D *= eqip.top();
					eqip.pop();
					answer++;
				}
			}
			else
			{
				D += top;
				monster.pop();
				answer++;
			}
		}
		else
		{
			answer += eqip.size();
			break;
		}
	}
	cout << answer << "\n";
	return 0;
}