[C++] 프로그래머스 디펜스 게임

https://school.programmers.co.kr/learn/courses/30/lessons/142085?language=cpp 

프로그래머스

풀이

라운드마다 적군 병사 수가 주어질 때, 현재 가진 병사와 무적권으로 최대 몇 라운드까지 버틸 수 있는지 구해야 하는 문제입니다.

 

보자마자 생각난 풀이는 라운드마다 적군의 크기를 알고 있으므로, 무적권을 greedy하게 사용하는 풀이입니다. 

for문을 사용하면 라운드 최대 크기가 1,000,000이기 때문에 2중 for문으로는 해결 할 수 없겠다 생각했습니다.

따라서, 이분탐색을 사용해서 최대 라운드를 가정하고 우선순위 큐를 사용해서 greedy하게 무적권을 사용했습니다. 

 

people 변수가 양수라면, 남은 병사가 존재하므로 현재 라운드를 버틸 수 있습니다. 따라서 답을 업데이트하고 다음 라운드를 검사합니다.  

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

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    int answer = 1;
    int enemySize = enemy.size(); 
    int left = 1;
    int right = enemy.size();
    
    // Binary Search
    while (left <= right) {
        int mid =  (left + right) / 2; //현재 라운드
        int unkillable = k;
        int people = n;
        priority_queue<int> pq;
        for (int i=0; i<mid; i++) {
            pq.push(enemy[i]); 
        }
        
        while (!pq.empty()) {
            int v = pq.top();
            pq.pop();
            
            if (unkillable > 0) unkillable--;
            else {
                people -= v;
            } 
            
            if (people < 0) break;
        }
        
        if (people < 0) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
            answer = mid;
        }
    }
    
    return answer;
}