코딩테스트 : 디펜스 게임

해당 문제는 준호가 가지고 있는 병사로 몇번째 라운드까지 막는지 검사하는 문제로 해당 문제의 핵심은 무적권을 어떻게 효율적으로 사용할지이다.

처음에는 가장 적의 수가 많은 라운드에 무적권을 사용하면 되지 않나 싶을 수 있다. 하지만 이렇게 하면 무적권을 사용하기 전 라운드에서 준호의 병사가 고갈되면 문제가 생긴다.

즉, 이미 진행한 라운드에서 가장 많은 적이 있는 라운드에 무적권을 사용하면 된다.

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

using namespace std;

// 주어진 병사 수와 무적권을 사용하여 최대 몇 라운드를 막을 수 있는지 계산하는 함수
int solution(int n, int k, vector<int> enemy) {
    int answer = -1; // 결과를 저장할 변수
    
    // 우선순위 큐의 비교 함수 정의 (내림차순)
    auto cmp = [](pair<int, int> p1, pair<int, int> p2){
        return p1.first < p2.first; // p1이 p2보다 작으면 true (내림차순)
    };
    
    // 우선순위 큐 초기화
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
    
    int round = 0; // 현재 라운드
    int sum = 0; // 소모된 병사 수의 합
    
    while (true) {
        // 병사 수가 남아있는 동안 라운드를 진행
        while (sum <= n) {
            // 모든 라운드를 막을 수 있는 경우
            if (round >= enemy.size()) {
                return enemy.size(); // 총 라운드 수 반환
            }
            pq.push(make_pair(enemy[round], round)); // 적의 수와 라운드 정보를 큐에 추가
            sum += enemy[round]; // 현재까지 소모된 병사 수 업데이트
            round++; // 다음 라운드로 이동
        }
        
        // 병사 수가 부족할 경우 무적권 사용
        if (k > 0) {
            auto temp = pq.top(); // 가장 많은 적을 가진 라운드 정보 가져오기
            sum -= temp.first; // 해당 라운드의 적 수만큼 소모된 병사 수 감소
            pq.pop(); // 우선순위 큐에서 제거
            k--; // 무적권 사용 횟수 감소
        } else {
            // 더 이상 병사 수가 부족하여 막을 수 없는 경우
            if (sum == n) // 병사 수가 정확히 소모된 경우
                return round; // 현재 라운드 수 반환
            else
                return round - 1; // 마지막으로 막을 수 있었던 라운드 수 반환
        }
    }
    
    return answer; // 기본적으로 unreachable, 반환값
}

해당 코드는 이미 진행한 라운드를 기록해두고 만약 병사수가 부족하고 무적권의 횟수가 남아있다면 무적권을 사용해 우선순위 큐에서 가장 높은(병사 수가 많았던 라운드) 라운드에 무적권을 사용하고 사용한 병력을 복구시킨다.