[Programmers] 디펜스 게임

무적권을 최대한 효율적으로 사용해야하는 문제였다.
즉, 가장 큰 수에 무적권을 사용하는 건데, 그렇다고 전체에서 가장 큰 수가 아니라, 자신이 갈 수 있는 지점까지 존재하는 수중 가장 큰 수이다.

처음에는 Dynamic Progrmming으로 다 해봐야하나 싶다가도 그러면 효율성이 말도 안될 것 같아서 고민하다가 질문하기에서 힌트를 봤다.

enemy의 최솟값을 이용했다는 말을 보고, 아차 싶었다.
나는 무적권을 최대값에 사용해야하기 때문에 계속 가장 큰 수들을 어떻게 골라낼 것인지 생각중이었는데, 일단 무적권을 다 쓰고 최솟값들을 n에서 빼주면 됐다.

priority_queue를 사용하면 간단하게 기능을 구현할 수 있었다.

#include <string>
#include <vector>
#include <queue>
using namespace std;

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