[BOJ/Silver 3] 백준 30701 돌아온 똥게임(C++)

문제 링크

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

30701번: 돌아온 똥게임

 

문제

 

 

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

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

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

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

 

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

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

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

 

입력

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

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

 

출력

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

 

예제 입력 1

5 5
1 2
1 3
1 10
2 2
1 40

예제 출력 1

4

예제 입력 2

8 3
2 5
1 4
1 2
1 10
2 7
1 50
1 264
1 999

예제 출력 2

7

 

노트

근호는 아직도 이 똥게임을 클리어하지 못하고 있다...

 

알고리즘 분류

• 그리디 알고리즘

 

풀이

방을 순서대로 돌파할 필요가 없으므로, 몬스터가 있는 방끼리 전투력을 기준으로 오름차순 정렬하고, 무기가 있는 방끼리 전투력을 기준으로 오름차순 정렬한다.

그리고 몬스터가 있는 방을 순서대로 돌파한다. 몬스터의 전투력보다 근호의 전투력이 더 높다면 현재 방을 돌파하고 다음 방을 탐색한다.

그게 아니라면 무기가 있는 방을 탐색하며 무기를 획득하고 전투력을 증가시킨다.

무기가 있는 방을 전부 돌파해서 전투력을 최대한 높였음에도 불구하고 다음 방에 존재하는 몬스터를 잡을 수 없다면 게임을 끝낸다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, A, M, W;
LL D, X;
vector<LL> Monsters, Weapons;
int Answer;

void input() {
    cin >> N >> D;
    for (int i = 0; i < N; i++) {
        cin >> A >> X;
        if (A == 1) {
            Monsters.push_back(X);
        }
        else {
            Weapons.push_back(X);
        }
    }
}

void settings() {
    sort(Monsters.begin(), Monsters.end());
    sort(Weapons.begin(), Weapons.end());
    while (1) {
        if (M < (int)Monsters.size()) {
            if (Monsters[M] < D) {
                D += Monsters[M];
                M++;
                Answer++;
            }
            else {
                if (W < (int)Weapons.size()) {
                    D *= Weapons[W];
                    W++;
                    Answer++;
                }
                else {
                    break;
                }
            }
        }
        else {
            if (W < (int)Weapons.size()) {
                D *= Weapons[W];
                W++;
                Answer++;
            }
            else {
                break;
            }
        }
    };
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}