[프로그래머스] - 디펜스 게임(C/C++)

프로그래머스

[문제 설명]

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

---

입출력 예

n	k	enemy	result
7	3	[4, 2, 4, 5, 3, 3, 1]	5
2	4	[3, 3, 3, 3]	4

---

[문제 풀이]

디펜스 게임 문제에서 제일 중요한 부분은 무적권을 사용하는 조건이다.

무작정 제일 큰 숫자 순서대로 써야 제일 이득이라는 생각이 들었다.

하지만, 주의해야 할 것은 무적권을 쓰기 전에 병사들이 다 사라질수도 있다는 점이다. 

 

따라서 언제 무적권을 사용해야 할지에 대해 고민해봐야한다.

그래서 생각난 방법은 아래와 같다.

현재 enemy 숫자를 계산하기 위한 enemySum 변수를 준비한다.

반복문을 통해 아래의 과정을 반복한다.

 

1. enemySum 변수에 현재 라운드의 enemy의 숫자를 더하고, priority_queue에 넣어준다.

=> priority_queue에 현재 라운드의 enemy값을 넣어주는 이유는 현재까지 더해진 각 라운드의 enemy값 중에 큰 값부터 빼내고 싶기 때문이다.

 

2-1. 만약 enemySum의 값이 병사의 값인 n보다 클 경우 priorty_queue의 맨 앞에 있는값(top)을 enemySum에서 빼주고, 

priority_queue에서 pop한다. k값도 1 감소시킨다.

=> k값을 감소시키는것에서 유추 할 수 있듯이 무적권을 사용한것이다.

 

2-2.enemySum의 값이 병사의 값인 n보다 크지만 k가 0

=> k값을 감소시키는것에서 유추 할 수 있듯이 무적권을 사용한것이다.

 

3. enemySum의 값이 n보다 작을 경우는 넘어간다.

 

4. 각 라운드의 마지막에 result 값을 1씩 증가시킨다.

 

5. 모든 라운드를 확인하거나 2번의 과정에 의해 종료될때까지 1~4의 과정을 반복한다.

 

예제 1번으로 예를 들어 설명하겠다.

n	k	enemy
7	3	[4, 2, 4, 5, 3, 3, 1]

 

Round 1

enemy : 4

priority_queue : {4}

k : 3

enemySum : 4

result: 1

=> enemySum이 n인 7보다 작으므로 넘어감

 

Round 2

enemy : 2

priority_queue : {4,2}

k : 3

enemySum : 6

result: 2

=> enemySum이 n인 7보다 작으므로 넘어감

 

Round 3

enemy : 4

priority_queue : {4,4,2} -> {4,2}

k : 3   ->   2

enemySum : 10 - 4 -> 6 

result: 3

=> enemySum이 n인 7보다 크므로 2-1번의 과정을 거침

enemySum에서 priority_queue의 top을 빼준다. (enemySum : 10 - 4 -> 6) , (priority_queue : {4,4,2} -> {4,2})

무적권을 사용했으니 k - 1 (k : 3 -> 2)

 

Round 4

enemy : 5

priority_queue : {5,4,2} -> {4,2}

k : 2   ->   1

enemySum : 11 -> 6 

result: 4

=> enemySum이 n인 7보다 크므로 2-1번의 과정을 거침

enemySum에서 priority_queue의 top을 빼준다. (enemySum : 11 - 5 -> 6) , (priority_queue : {5,4,2} -> {4,2})

무적권을 사용했으니 k - 1 (k : 2 -> 1)

 

Round 5

enemy : 3

priority_queue : {4,3,2} -> {3,2}

k : 1   ->   0

enemySum : 10 -> 6 

result: 5

=> enemySum이 n인 7보다 크므로 2-1번의 과정을 거침

enemySum에서 priority_queue의 top을 빼준다. (enemySum : 10 - 4 -> 6) , (priority_queue : {4,3,2} -> {3,2})

무적권을 사용했으니 k - 1 (k : 1 -> 0)

 

Round 6

enemy : 3

priority_queue : {3,3,2}

k : 0

enemySum : 8 

result: 5

=> enemySum이 n인 7보다 크고 k의 값이 0이므로 2-2번의 과정을 거침

무적권을 사용할 수 없고, enemy의 숫자가 n보다 크므로 해당 라운드는 클리어 할 수 없다.

Round 5까지 클리어 할 수 있으므로 리턴해야할 정답은 5이다. 

 

위와 같은 방식을 토대로 코드를 작성하면 된다.

 

[코드]

[GitHub]

GitHub - EGyeom/ProblemSolving

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(int n, int k, vector<int> enemy) {
    int answer = 0;
    int enemySize = enemy.size();
    if(k >= enemySize)
        return enemySize;
    
    priority_queue<int> pq;
    
    int enemySum = 0;
    for(int i = 0; i < enemySize; i++)
    {
        pq.push(enemy[i]);

        enemySum += enemy[i];
        if(enemySum > n)
        {
            if(k <= 0) break;
            enemySum -= pq.top();
            pq.pop();
            k--;
        }
        answer++;
    }
    return answer;
}