[프로그래머스] Level 2. 디펜스 게임

https://school.programmers.co.kr/learn/courses/30/lessons/142085#

프로그래머스

해결 방법

• 라운드를  하나씩 진행하면서 합 sum을 구해간다.
• sum이 n보다 커지는 순간이 오면, pq에 있는것중 가장 값이 큰값(pq.top()) 을 하나씩 꺼내면서, sum이 n보다 작아질때까지 티켓을 사용한다. 
• 만약 티켓이 없어서 sum을 n보다 줄이지 못한다면 그 라운드에서 실패한다는 의미이므로, 바로 round를 리턴한다.

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

using namespace std;

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

 

 

핵심은 "가장 cost가 큰 라운드를 어떻게 찾아내서 티켓사용할래?" 인 문제였다고 생각한다. priority queue를 사용하면 내부적으로 값이 큰것부터 알아서 꺼내주기 때문에 참으로 편하다.