[Algorithm] Programmers :: 디펜스 게임

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

프로그래머스

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

무적권을 사용하면서 최대한 얼마나 오래 생존할 수 있는가를 구하는 문제다.

그렇다면 '언제' 무적권을 사용하는게 제일 효율적인가를 알아내는게 중요하다.

단순히 특정라운드에서 비교를 통해 죽기직전에만 쓰는건 정답이 아니다.

왜냐하면 무적권을 쓰더라도 최대한 많은 병사를 생존시키지 않으면 다음라운드때 또 바로 라운드가 종료되어버릴 수 있기 때문이다.

 

그렇기 때문에 라운드를 진행하면서 우선순위큐에 몬스터의수만큼 숫자를 집어넣는다. 우선순위큐는 큰값부터 꺼내게 한다. 즉, 무적권이 필요할 때 우선순위큐에서 값을 꺼내서 사용한다.

우선순위큐의 top은, 현재라운드까지 진행하면서 만났던 몬스터들 중 가장 큰값임과 동시에 무적권으로 처리할 수 있는 가장 많은 몬스터 수이다.

 

그렇게 저장만 하고 진행하다가 만약 종료되어버릴 조건이 된다면(병사수 < 몬스터수) 무적권이 있다는 가정하에 우선순위큐에서 꺼내서 쓰는것이다. 즉, 과거에 써버리고 바로 현실에 반영되는 것이다.