[프로그래머스 C++] 더 맵게

 

[프로그래머스 C++] 더 맵게

 

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

프로그래머스

---

 

해결전략

 

힙 Heap

priority queue

 

 priority_queue<int, vector<int>, greater<int>> pQ; // 오름차순

 

---

 

코드

 

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

int solution(vector<int> sco, int K) {
    int answer = 0;
    
    priority_queue<int, vector<int>, greater<int>> pQ; // 낮은값이 위로 오도록 오름차순 정렬
    
    for(int i=0; i<sco.size(); i++){
        pQ.push(sco[i]); // pQ에 음식 정보를 담는다.
    }

    while(!pQ.empty())
    {
        if (pQ.top() >= K) break; // pQ의 모든 음식이 K이상이면 while문 종료 

        if (pQ.size() == 1 && pQ.top() < K) // pQ의 남은 음식이 1개이고 해당 음식이 K보다 작으면
            return -1; // -1 리턴

        int leastSco = pQ.top();
        pQ.pop();
        int secondSco = pQ.top();
        pQ.pop();

        int newFood = leastSco + (secondSco * 2);
        pQ.push(newFood);

        answer++;
    }

    return answer;
}

 

---