문제 출처

1. 문제설명

• 처음에 n명의 병사를 가지고 있다.
• 매 라운드마다 공격해오는 적 enemy의 공격을 막아야 한다.
• 병사가 몇명이든 한 라운드를 무적권 k를 1회 사용해 적을 막을 수 있다.
• 단, 최대한 많은 라운드를 막아야 한다.
• 몇 라운드까지 막을 수 있는지 구하라

2. 알고리즘 설계

• enemy의 길이가 1,000,000이므로, $O(NlogN)$으로 풀이
• min_heap을 사용해 순차적으로 정렬

3. 로직

• 한 번에 저장하는 것이 아니라, 하나씩 저장하면서 상태를 파악하는 방식
• pq에 넣다가 무적권 개소를 넘어서면 현재 저장된 가장 작은 값을 sum
• 만약 sum이 n보다 커지면 현재 루프 순서 리턴
• 최소값만 n을 이용해 더해주고, 나머지는 무적권을 사용해 방어

4. 전체 코드

#include <bits/stdc++.h>
using namespace std;

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