프로그래머스 디펜스 게임 [Lv.2] (C++)

프로그래머스

준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.

 

 

풀이 방법

디펜스 게임 문제는 무적권을 어디서 사용해야 하는가에 있습니다.

그렇기 때문에 순차적으로 진행해야하는 유저의 입장에서 생각하면 풀이가 불가능합니다.

 

유저의 입장에서 순차적으로 게임을 진행해 보면, "아 그때, 무적권을 써야 했구나~"라는 순간이 옵니다.

해당 문제는 "그 때, 무적권을 썼다 치자"를 반복하여 풀이합니다.

 

priority_queue<int> q;

int r = 0;
for (; r < enemy.size(); r++)
{
    q.push(enemy[r]);
    n -= enemy[r];

우선순위 큐를 이용하여 지금까지 만난 적의 무리 중 가장 큰 수를 볼 수 있게 해줍니다.

 

while (!q.empty() && n < 0 && k > 0)
{
    n += q.top();
    q.pop();
    k--;
}

 

이후 무적권을 쓰지 않으면 더이상 진행이 불가능 할 때, 우선순위 큐에서 해당 수를 꺼내어 무적권 사용했다 치기를 반복합니다.

 

if (n < 0)
    break;

그런 이후에도 병사의 수가 0보다 작다면 게임을 종료합니다.

 

 

 

정답 코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    
    priority_queue<int> q;
    
    int r = 0;
    for (; r < enemy.size(); r++)
    {
        q.push(enemy[r]);
        n -= enemy[r];
        
        while (!q.empty() && n < 0 && k > 0)
        {
            n += q.top();
            k--;
            q.pop();
        }
        
        if (n < 0)
            break;
    }
   
    return r;
}