[ 프로그래머스 C++ ] 디펜스 게임 lv2

해설

우선순위 큐를 이용해 풀어야 하는 문제이다.

제한 사항을 보면 enemy 의 길이는 백만이므로 for문은 한번만 써야 한다는 것을 알 수 있다.

 

for문을 돌면서 우선순위 큐 안에 값들을 집어 넣고, 큐의 길이가 무적권의 갯수보다 클 때 큐의 맨 앞의 값을 꺼내 n에서 빼준다. 무조건 무적권의 개수만큼은 스테이지가 진행될 수 있기 때문이다. 무적권의 개수가 벡터보다 클 때 는 모든 스테이지를 통과한 것이므로 벡터의 사이즈를 리턴해준다.

 

우선순위 큐를 코딩테스트 하면서도 잘 사용해보지 않았는데 이렇게 한번씩 나올 때마다 공부하는 느낌이 들어서 좋은것 같다.

---

문제 설명

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.

• 준호는 처음에 병사 n명을 가지고 있습니다.
• 매 라운드마다 enemy[i]마리의 적이 등장합니다.
• 남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
  • 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
  • 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
• 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
• 무적권은 최대 k번 사용할 수 있습니다.

준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ n ≤ 1,000,000,000
• 1 ≤ k ≤ 500,000
• 1 ≤ enemy의 길이 ≤ 1,000,000
• 1 ≤ enemy[i] ≤ 1,000,000
• enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.
• 모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 해주세요.

---

코드

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

using namespace std;

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