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

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

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    int answer = enemy.size(); //모든 라운드 버팀 상정
    
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i=0; i<enemy.size(); i++)
    {
        pq.push(enemy[i]);
        
        if(pq.size() > k)
        {
            n -= pq.top(); //병사 사용
            pq.pop();
        }
        
        if(0 > n) //병력 소진
        {
            answer = i;
            break;
        }
    }
    return answer;
}

 

우선순위 큐를 활용한 문제이다.

우선 answer를 모든 라운드 버팀이 가능하다는 상정을 하고 시작한다.

 

적이 적은 수부터 정렬하기 위해 pq를 오름차순으로 정렬하고, 적의 수를 넣어준다.

그리고 pq의 사이즈가 k보다 크면 병사를 사용한다.

이는 k(무적권)을 가능한 많은 적일 때 사용하기 위함이다.

 

이를 반복하여 병사가 음수가 되면 해당 라운드 값을 반환한다.

여기서 i를 반환하는 것은 반복문에서 i=0부터 시작하고, 라운드는 1부터 세기 때문이다.