Level 2. 디펜스 게임

Level 2. 디펜스 게임

 

 

정답이 몇 라운드가 되던지, 그 중 무적권을 사용한 라운드는 가장 몬스터가 많이 나오는 n개여야 하므로 우선순위 큐를 사용해야 할 것 같았다.

• 이번 문제는 솔직히 당연히 틀릴 줄 알고 제출했는데 정답 처리돼서 당황스러웠다.

 

무적권을 사용할 수 있으면 일단 사용하고 최소힙에 넣는다.

 

이후 무적권이 없을 때부터는 최소힙의 최솟값과 현재 라운드의 몬스터 수를 비교해, 이전에 썼던 것보다 현재 라운드에 쓰는 게 이득이면 이전 라운드의 몬스터 수를 n에서 빼고 현재 라운드에 무적권을 사용한다.

• 나중에 현재 라운드에 사용한 것보다 이득인 상황이 올 수 있으므로, 현재 라운드의 몬스터 수도 최소힙에 넣어 주어야 한다.

 

현재 라운드보다 이전에 썼던 것이 이득이면, 현재 라운드의 몬스터 수를 그냥 n에서 뺀다.

 

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

using namespace std;

int solution(int n, int k, vector<int> enemy)
{
    int ans;
    priority_queue<int, vector<int>, greater<int>> prQue;

    for (ans = 0; ans < enemy.size(); ++ans)
    {
        if (0 < k)
        {
            --k;
            prQue.emplace(enemy[ans]);
        }
        else if (!prQue.empty() && prQue.top() < enemy[ans])
        {
            n -= prQue.top();
            prQue.pop();
            prQue.emplace(enemy[ans]);
        }
        else
        {
            n -= enemy[ans];
        }

        if (n < 0)
            return ans;
    }

    return ans;
}