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

최초 업로드: 2025-11-15 17:48:35

최근 수정 시간: 2025-11-15 17:48:35

게시자: rlatjwls3333

카테고리: 백준

# [Silver III] 돌아온 똥게임

[문제 링크](https://www.acmicpc.net/problem/30701)

## 문제 설명

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

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

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

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

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

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

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

## 입력

첫 번째 줄에는 방의 수 $N$과 근호의 시작 전투력 $D$가 공백으로 구분되어 정수로 주어진다. ($1\leq N\leq 100\,000;$ $1\leq D\leq 10^9$)

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

## 출력

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

## 풀이
장비와 몬스터를 따로 입력받아 오름차순으로 정렬한 후, 몬스터를 못잡을 때 장비를 사용하는 방식으로 구현했습니다. 만약 장비를 착용했을 때 전투력이 10억이 넘어가면 항상 모든 몬스터를 잡을 수 있기에 n을 출력하고 종료해주었습니다.

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

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 long long n, d; cin >> n >> d;
 vector<int> monster, armor;
 for(int i=0;i<n;i++) {
 int a, x; cin >> a >> x;
 if(a==1) monster.push_back(x);
 else armor.push_back(x);
 }
 sort(monster.begin(), monster.end());
 sort(armor.begin(), armor.end());

int cnt=armor.size(), idx1=0, idx2=0;
 while(idx1<monster.size() || idx2<armor.size()) {
 bool change=false;
 while(idx1<monster.size() && d>monster[idx1]) {
 cnt++;
 change=true;
 d += monster[idx1++];
 }
 if(idx2<armor.size()) {
 change=true;
 d *= armor[idx2++];
 if(d>1'000'000'000) {
 cout << n;
 return 0;
 }
 }
 if(!change) break;
 }
 cout << cnt;
}
```