[programmers] 디펜스 게임

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

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

priority_queue를 사용해 현재 턴까지 진행된 게임의 enemy 수를 내림차순으로 저장해 두고,

필요할 경우(K를 사용해야 턴을 진행할 수 있는 경우)마다 K를 사용하면 pq에서 pop해주는 방식.

 

------------------------------------------------------풀이-------------------------------------------------

 

총 enemy의 수만큼 turn을 진행.

0부터 시작되어야 게임 종료 시점을 turn에 포함시키지 않을 수 있다.

turn이 시작되면 pq에 현재의 enemy를 저장하고,

사용 가능한 병사 수 N에서 enemy 수를 뺀다.

만약 N이 0 이상이면 그냥 진행 가능한 것이고, 안 되면 K를 사용해서 N을 0 이상으로 만들어준다.

둘다 해당하지 않으면 게임을 진행할 수 없는 것이므로 종료한다.

 

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

using namespace std;

int N, K;
vector<int> Enemy;
priority_queue<int, vector<int>, less<int> > pq;

// 현재 적 수(e) 만큼 K를 사용해서 만들어낼 수 있는가
bool can_fight(){
    while(K > 0 && !pq.empty()){
        N += pq.top();
        pq.pop();
        K--;
        if(N >= 0){
            return true;
        }
    }
    return false;
}

int play_game(){
    int turn = 0;
    for(turn = 0; turn < Enemy.size(); turn++){
        // 턴 진행
        pq.push(Enemy[turn]);
        N -= Enemy[turn];
        // 그냥 진행 가능하면 진행. 안 되면 K 사용해서 시도
        if(N >= 0 || can_fight()){
        }
        else{
            // 안되면 종료
            break;
        }
    }
    return turn;
}

int solution(int n, int k, vector<int> enemy) {
    int answer = 0;
    N = n; K = k; Enemy = enemy;
    answer = play_game();
    return answer;
}

 

------------------------------------------------------후기-------------------------------------------------

 

처음에는 N이 enemy 이상일 때만 pq에 넣는 방식으로 진행했는데,

문제는 그럼 예제 2번처럼 N이 enemy 수보다 작지만 K가 enemy 수만큼 존재할 경우에 문제가 발생한다.

현재 값에 K를 사용하는 것을 고려하지 못해, 문제가 발생하는 것이다.