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

문제

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

프로그래머스 더 맵게

프로그래머스 더 맵게

 

문제 내용

음식들의 지수가 모두 K 이상이 되기 위해 몇 번의 연산이 필요한지를 출력하면 된다. (불가능하면 -1 출력)

연산은 (가장 낮은 지수 + 그 다음으로 낮은 지수*2) 로 계산되며, 사용된 음식은 사라지고 연산에 의해 새로운 음식이 추가된다고 생각하면 된다.

 

문제 풀이

우선순위큐로 문제를 쉽게 해결할 수 있다.(heap)

이때 우선순위 큐의 사이즈에 주의하자. 원소가 없는데 top(), pop() 연산을 하면 에러가 난다. (한참 헤맸다)

 

코드

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

using namespace std;

int solution(vector<int> scoville, int K) {
    priority_queue<int, vector<int>, greater<int>> pq; //오름차순으로 되게

    for(auto num:scoville){
        pq.push(num);
    }

    
    int cnt=0;
    while(pq.top() < K){
        if(pq.size()<=1){
            return -1;   
        }
        
        int first=pq.top();
        pq.pop();
        int second=2*pq.top();
        pq.pop();
        pq.push(first+second);
        cnt++;
    }
    
    return cnt;
}