[프로그래머스/Level 3] 야근 지수 (C++)

programmers.co.kr/learn/courses/30/lessons/12927

코딩테스트 연습 - 야근 지수

문제에서 야근 지수를 최소화 하기 위해서는 작업량의 최대값을 매번 줄여가야합니다. 이러한 최대값을 구하기 위해서 우선순위 큐를 이용한다면, 문제를 쉽게 해결할 수 있습니다.

 

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

long long solution(int n, vector<int> works) {
    long long answer = 0;
    priority_queue<int, vector<int>, less<int> > pq;
    
    for(auto w : works) {
        pq.push(w);
    }
    
    while(n--) {
        if(pq.top() > 0) {
            int num = pq.top();
            pq.pop();
            pq.push(--num);
        }
    }
    
    while(!pq.empty()) {
        long long num = pq.top();
        pq.pop();
        answer += num * num;
    }
    
    return answer;
}