[C++]백준 - 22993번 문제

22993번: 서든어택 3 (acmicpc.net)

22993번: 서든어택 3

 

22993번 : 서든어택 3

---

지스타를 준비하기 시작한 작년 여름 이후 CBT와 런칭 준비를 한 오늘까지. 평일 저녁에 가족이 깨어 있는 것을 거의 본 적이 없다.

이제 본격적인 정식오픈을 이틀 앞 둔 오늘. 바람소리와 스산한 빗소리가 사무실 창밖을 때린다.

폭풍전야.

블라인드에서 서든3을 비웃던, 지금도 비웃는 이들에게 반박글을 달지 않았다. 

니들이 허접한지, 우리가 허접한지는 결과가 말해줄 것이다.

넥슨의 게임 개발자 준원이는 서든어택 3의 출시를 앞두고 게임 테스트를 하고 있다.

맵에는 준원이를 포함해 N명의 플레이어가 있다. 준원이의 공격력은 A1이고, 나머지 사람들의 공격력은 A2,⋯,AN이다.

전투가 시작되면 누구나 누구든 공격할 수 있게 된다! 죽은 사람은 공격하거나 공격받지 못하고, 두 사람이 동시에 공격하는 일은 일어나지 않는다.

공격력이 X인 플레이어 A가 공격력이 Y인 플레이어 B를 공격하면,

•  X > Y 이면, B가 죽고 A의 공격력은 X+Y가 된다.
• X < Y 이면, A가 죽고 B의 공격력은 X+Y가 된다.
•  X = Y 이면, 아무 일도 일어나지 않는다.

드디어 전투가 시작되었다! 준원이는 최후의 생존자가 될 수 있을까?

 

입력

---

첫째 줄에는 준원이를 포함한 플레이어의 수 N이 주어진다.

둘째 줄에는 각 플레이어의 공격력 A1,⋯,AN이 차례대로 공백을 사이에 두고 주어진다.

•  1≤N≤100000
•  1≤Ai≤1000000000 (1≤ i ≤N)

 

 

출력

---

좋은 전투 순서가 존재해서 준원이만 생존하고 나머지 플레이어가 모두 죽게 만들 수 있다면 Yes를, 반대로 전투가 어떤 순서로 이루어져도 준원이가 절대 최후의 생존자가 될 수 없다면 No를 출력한다.

 

 

---

 

생각해 볼 점

---

우선, 준원이의 공격력을 저장한 후,

 

최선의 전투 순서는 오름차순으로 진행되는 것이므로, 나머지 사람들의 공격력은 최소힙에 넣어줍니다.

 

그러면 자동으로 오름차순으로 pop()을 진행할 수 있습니다.

 

힙이 비어버릴 때까지 다음 순서로 진행합니다.

 

1. 최소 힙에서 pop()합니다.

2. pop된 공격력이 준원의 공격력보다 낮으면 준원의 공격력에 더해줍니다.

3. 그렇지 않으면, No를 출력하고 종료합니다.

 

힙이 모두 비어서 준원이 승리했다면, Yes를 출력하고 종료합니다.

 

코드

---

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

typedef long long ll;

int main()
{
    int N;
    scanf("%d", &N);
    
    ll Junwon;
    scanf("%lld", &Junwon);
    
    //최소 힙
    priority_queue<int, vector<int>, greater<int>> power;
    
    //입력부
    for(int i = 1; i < N; i++)
    {
        int input;
        scanf("%d", &input);
        power.push(input);
    }
    
    while(!power.empty())
    {
        int next = power.top();
        power.pop();
        
        if(next < Junwon) Junwon += next;
        
        //승리가 불가능하면 종료
        else
        {
            printf("No");
            return 0;
        }
    }
    
    printf("Yes");
    return 0;
}

 

그 외

---

int 범위를 충분히 넘어갈 만 하므로, long long타입을 이용해 계산해주시기 바랍니다.

 

여담으로는 이 문제 지문이 참 재밌네요~ 서든어택 3가 발매될 날을 기대하겠습니다.