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

코딩테스트 연습 - 디펜스 게임 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

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

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

우선순위큐라는 힌트를 알면 쉽게 풀리지만, 그것을 떠올리기 어려웠던 문제.

 

어떤 식으로 진행되냐 하면은

priority_queue<int, vector<int>, greater<int>> pq;이런 식으로 선언하면 가장 작은 값이 top에 오게 됨

pq에 계속 enemy의 값을 더해주다가, 아래쪽에 깔린 k만큼의 값은 어차피 '무적권'을 쓰면 무조건 해결이 되니 신경쓰지 말고

그 위에 값들에 한해서 n이라는 값에 대한 조건을 만족하는지만 확인해주면 된다.

나는 이를 n에 temp라는 그때그때 새로 할당되는 top(,할당 후에는 pop이 되는 )값을 빼주고 이것이 0보다 작으면 for문 자체를 break시켰다.

이렇게 되면 push할 때마다 answer이 더해지던 것이 멈추게 되므로 답을 구할 수 있따.