[프로그래머스] 디펜스 게임 c++ (우선순위 큐)

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/142085

프로그래머스

---

풀이

최대한 많은 라운드를 진행시켜야 한다.

필자가 생각한 방법은 아래와 같다.

1. 우선 막지 못할때까지 병사를 소모한다.

2. 막지 못할 경우, 가장 많은 병사를 사용했던 곳에 무적권을 사용한다. (priority_queue)

3. 무적권을 다 쓰면 종료한다.

 

따라서, for문을 순회하며 priority_queue에 병사의 수를 push 하고, 무적권이 있는 경우 우선순위 큐에서 꺼내며 사용했던 병사를 복구하는 방법으로 구현하였다.

---

코드

#include <bits/stdc++.h>

using namespace std;

priority_queue<int> pq;

void use_coupon(int &n, int &k, vector<int> &enemy) { 
    k--;
    if(!pq.empty()) {
        n += pq.top();
        pq.pop();
    }
}

int solution(int n, int k, vector<int> enemy) {
    int answer = 0;
    
    for(int i = 0; i < enemy.size(); i++) {
        n -= enemy[i];
        pq.push(enemy[i]);
        if(n < 0) {
            if(k == 0) break;
            use_coupon(n, k, enemy);
        }
        answer++;
    }
    
    return answer;
}