[프로그래머스] 디펜스 게임 C++ 풀이 및 해설

 

https://school.programmers.co.kr/learn/courses/30/lessons/142085

프로그래머스

 

풀이 방법

먼저, 무적권을 사용하지 않고 갈 수 있는 라운드까지 최대한 가본다.

이때 지나온 라운드들의 적군들의 수를 우선순위 큐에 넣어 관리한다. ( 뽑으면 최대 적군들의 수가 나올 수 있게 )

라운드 최대한 갔더니 이제 보유한 병사로 전투를 할 수 없는 상황이 왔다.

 

이제. 무적권을 사용하는 것이다.

무적권의 사용 방법은 다음과 같다. 

우선순위 큐에서 이제껏 전투해온 적군의 수가 많은 라운드를 뽑는다. 우선 순위 큐에서 한번 pop한다.

그 크기만큼 내 병사들을 + 해준다. 왜냐면 큐에서 pop한 그 라운드에서 무적권을 사용했다고 가정하는거다.

최대한 많은 라운드를 앞으로 나가야하니

이전 전투에서 적군의 병사가 많았던 라운드에서 무적권을 사용하는것은 당연하다!

 

그리고 과거 라운드에서 무적권을 사용했으니

현재 라운드에서 상대 적군만큼 - 해준다. 그리고 우선순위 큐에 현재 라운드의 적군수 push.

 

이런 로직으로 문제를 풀면 된다!

 

전체 코드

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

int solution(int n, int k, vector<int> enemy) {
    priority_queue<int, vector<int>, less<int>> pq;
    
    int i=0;
    for(; i<enemy.size(); i++) {
        if(n-enemy[i]>=0) {
            n-=enemy[i];
            pq.push(enemy[i]);
        } else {
            if(k>=1) {
                if(!pq.empty() && pq.top() >= enemy[i]) { //pq.top() >= enemy[i]....
                    n+=pq.top();
                    pq.pop();
                    
                    n-=enemy[i]; // 주의. 무적권을 사용하더라도 pq에 push 해줘야함.
                    pq.push(enemy[i]);
                }
                k--; // 지난 라운드에 손해본 병사가 없어도 쉴드는 사용할 수 있으므로 여기에서 k-- 존재.
            } else {
                break;
            }
        }
    }
    
    
    return i;
}