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

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

프로그래머스

 

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

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

 주어진 몬스터의 공격을 최대한 많이 막아낼 때, 몇라운드까지 막을 수 있는가가 문제이다. 

 

언제 방어권을 사용할 것인가? 가 가장 중요한 문제인데, 

처음엔 가장 큰 수에 대해서 방어하면 되겠다 생각했지만 방어권을 사용할 기회가 오기전에 게임이 종료될수도 있으니 이 또한 계속 따져야한다. 이를 for문을 돌며 하나씩 판단하려하니 머리가 너무 복잡해졌다.

 

하지만 우선순위큐(최소힙)을 사용하면 아주 간단하게 해결할 수 있다. 

 

우선순위큐에는 방어권을 사용할 라운드의 몬스터 수가 들어가게 된다. 

그러면 아래와 같이 문제를 풀어갈 수 있다.

 

1. 우선순위큐의 크기 > 방어권 수 이면 

가장 작은 수를 방어권 대신 직접 받아낸다. 

 

2. 받아낸 몬스터 수보다 기존 체력인 n 이 더 작다면 게임을 종료한다.

 

최소힙이기 때문에 꺼낼때는 O(1)의 시간이 걸리며 삽입시에도 O(log n) 시간이 걸리기 때문에 효율적이라 할 수 있다. 

 

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

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

위의 알고리즘을 코드로 옮긴 결과이다. 

먼저 큐에 데이터를 넣고 만약 방어권 수보다 큐의 크기가 커졌다면 그만큼 공격을 직접 받아내야한다. 

이 때, 최선의 선택은 가장 데미지가 약한 라운드를 받아내는 것이다. 

따라서 최소힙에서 top을 꺼내 데미지를 받는다. 

 

그 후, 체력이 남아 있다면 반복문을 진행한다. 

 

위와 같이 그때그때의 최선의 선택을 통해, 최적의 결론을 이끌어내는 방식이 그리디 알고리즘이다. 

그리디 알고리즘을 큐로도 구현가능하다는 점을 인지해두어야겠다.