fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 30701 (C++) 돌아온 똥게임
최초 업로드: 2025-11-15 17:48:35
최근 수정 시간: 2025-11-15 17:48:35
게시자: rlatjwls3333
카테고리: 백준
조회수: 7
# [Silver III] 돌아온 똥게임 [문제 링크](https://www.acmicpc.net/problem/30701) ## 문제 설명 <p style="text-align: center;"><img alt="" src="https://u.acmicpc.net/406344fd-9cb0-4f9f-9cea-447317ef269a/%EB%98%A5%EA%B2%8C%EC%9E%84.png" style="height: 50%; width: 50%;"></p> <p>유튜브에서 똥게임 광고를 지나치게 많이 본 근호는 본인이 직접 똥게임을 설치해서 하기로 했다.</p> <p>처음에 근호는 $D$의 전투력을 가지고 시작한다. 근호 앞에는 $N$개의 방이 있는데, 각 방에는 몬스터 또는 장비가 있으며 $i(1\leq i\leq N)$번째 방에 있는 몬스터 또는 장비는 전투력 $X_i$를 가진다.</p> <p>근호는 매번 아직 돌파하지 않은 방 중 어떤 방에 먼저 들어갈지 자유롭게 정할 수 있으며, 들어간 방에 있는 내용물에 따라 다음과 같이 행동한다.</p> <ul> <li>몬스터가 있는 경우: 근호의 전투력이 몬스터의 전투력보다 크면 몬스터를 쓰러뜨릴 수 있으며, 이후 근호의 전투력에 몬스터의 전투력이 더해진다. 근호의 전투력이 몬스터의 전투력보다 작거나 같을 경우 근호는 패배한다.</li> <li>장비가 있는 경우: 근호의 현재 전투력에 상관없이 얻을 수 있으며, 근호의 전투력에 장비의 전투력이 곱해진다. 단, 현재 얻고자 하는 장비보다 전투력이 작은 모든 장비를 얻어야만 현 장비를 얻을 수 있다.</li> </ul> <p>방에 있는 몬스터를 쓰러뜨리거나 장비를 얻을 경우 해당 방을 돌파한 것이며, 근호가 모든 방을 돌파하거나 몬스터에게 패배했을 경우 게임이 끝난다.</p> <p>근호가 최선의 전략으로 게임을 진행할 때, 최대로 돌파할 수 있는 방의 수를 구하여라.</p> <p>근호가 게임 중 행동을 통해 올릴 수 있는 전투력에 상한이 없음에 유의하자.</p> ## 입력 <p>첫 번째 줄에는 방의 수 $N$과 근호의 시작 전투력 $D$가 공백으로 구분되어 정수로 주어진다. ($1\leq N\leq 100\,000;$ $1\leq D\leq 10^9$)</p> <p>다음 $N$개 줄에는 한 줄에 하나씩 방의 정보 $A_i,X_i$가 공백으로 구분되어 정수로 주어진다. $A_i$는 $1$ 또는 $2$이며, $1$이면 몬스터가 있는 방이고 $2$이면 장비가 있는 방이다. $X_i$ $(2\leq X_i\leq 10^9)$는 해당 방에 있는 몬스터 또는 장비가 가진 전투력이다.</p> ## 출력 <p>첫 번째 줄에 근호가 최대로 돌파할 수 있는 방의 수를 출력한다.</p> ## 풀이 장비와 몬스터를 따로 입력받아 오름차순으로 정렬한 후, 몬스터를 못잡을 때 장비를 사용하는 방식으로 구현했습니다. 만약 장비를 착용했을 때 전투력이 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; } ```