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

문제

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 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 해주세요.

---

내가 풀이한 알고리즘을 요약하자면 아래와 같다.

1) n >= enemy[round] 이면 무적권을 사용하지 않고 디펜스

2) n < enemy[round] 이면 무적권을 사용하여 디펜스

2-1) pq.top() >= enemy[round] 이전에 디펜스한 라운드에 무적권을 사용

2-2) pq.top() < enemy[round] 현재 라운드에 무적권을 사용

3)디펜스 실패 게임 종료

 

1)현재 라운드에서 남은 병사가 적군의 수보다 많다면 무적권을 사용하지 않고 디펜스한다.

이때, 각 라운드 마다 무적권을 사용하지 않고 디펜스한 적군의 수를 우선순위큐에 저장한다.

(priority_queue(=pq)의 경우 default는 maxhaep이기 때문에 root에 최대값이 유지 됨)

 

2)무적권을 사용하지 않고 디펜스가 불가능해 지면 무적권을 사용한다.

이때 무적권을 사용하는 조건을 아래와 같이 두 가지 경우로 나뉜다.

2-1)pq.top() >= enemy[round]

2-2)pq.top() < enemy[round]

pq.top은 무적권을 사용하지 않고 디펜스한 라운드들 중 가장 많은 적군의 수가 저장되어 있다.

즉, 1round : 4명 2round : 7명을 막았다면 pq.top()은 7을 반환할 것이다.

우리는 각 라운드들 중에 가능하면 적군이 많은 라운드에 무적권을 사용해야 최대한 많은 라운드를 디펜스 할 수 있다.

따라서 현재 라운드와 디펜스한 라운드 중 어느 쪽의 적군 수 가 많은지 비교하여

현재 라운드에 무적권을 사용할지 이미 디펜스한 라운드에 무적권을 사용할지 판단하는 것이다.

 

문제의 예시로 동작 과정을 살펴보자. ( n = 7, k = 3, enemy = {4, 2, 4, 5, 3, 3, 1} )

Round1 : enemy = {4, 2, 4, 5, 3, 3, 1}, k = 3  -> 무적권 x

n = 7 - 4 = 3, pq = { 4 } (빨간색 = pq.top() )

 

Round2 : enemy = {4, 2, 4, 5, 3, 3, 1}, k = 3 -> 무적권 x

n = 3 - 2 = 1, pq = { 4, 2 }

 

Round3 : enemy = {4, 2, 4, 5, 3, 3, 1}, k = 3 -> 1라운드에 무적권 사용

pq.top() = 4, enemy[3] = 4이므로 2-1)pq.top() >= enemy[round] 조건에 따라 1라운드에 무적권을 사용한다.

1라운드에 소모한 병사를 복구하면 n = 1 + 4 = 5

이후 3라운드를 디펜스하면

n = 5 - 4 = 1, pq = { 2, 4 } -> 1라운드에 4가 pop되고 3라운드의4가 push된 상태

 

Round4 : enemy = {4, 2, 4, 5, 3, 3, 1}, k = 2 -> 4라운드에 무적권 사용

pq.top() = 4, enemy[4] = 5이므로 현재 라운드에 무적권을 사용하는 것이 이득이기 때문에 2-2)조건에 따라 현재 라운드에 무적권을 사용한다. 따라서 n과 pq는 변경사항이 없다.

n = 1, pq = {2, 4}

 

Round5 : enemy = {4, 2, 4, 5, 3, 3, 1}, k = 1 -> 3라운드에 무적권 사용

pq.top() = 4, enemy[5] = 3이므로 2-1)조건에 따라 3라운드에 무적권을 사용한다.

3라운드에 소모한 병사를 복구하면 n = 1 + 4 = 5

이후 5라운드를 디펜스하면

n =  5 - 3 = 2, pq = {2, 3} -> 3라운드의 4가 pop되고 5라운드의 3이 push된 상태

 

Rount6 : enemy = {4, 2, 4, 5, 3, 3, 1}, k = 0

현재 병사 2명이 현재 라운드의 적군 수 3보다 적으면서 더이상 무적권이 남아있지 않으므로 게임 종료

 

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

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    priority_queue<int, vector<int>> pq; 
    int round = 1;
    for (int r = 0; r < enemy.size(); r++) {
        //1)무적권을 사용하지 않고 디펜스
        if (n >= enemy[r]) {
            pq.push(enemy[r]);
            n -= enemy[r];
        }
        else {
            //2)무적권을 사용하여 디펜스
            if (k) {
                k--;
                if (!pq.empty()) {
                    int temp = pq.top();
                    pq.pop();
                    //2-1)이전에 디펜스한 라운드에 무적권을 사용
                    if (temp >= enemy[r]) {
                        n += temp - enemy[r];
                        pq.push(enemy[r]);
                    }
                    //2-2)현재 라운드에 무적권을 사용
                    else pq.push(temp);
                }
            }
            //3)디펜스 실패 게임 종료
            else return r;
        }
    }
    return enemy.size();
}