[C++] 프로그래머스 야근 지수

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

프로그래머스

풀이

작업량의 제곱합을 최소화 하기 위해, 최대 작업을 낮추면 되는 문제이다.

처음엔 모든 작업량을 더한 후 n시간을 빼주고, 남은 시간을 작업량 크기에 맞게 분배하려고 했다. 근데, 이렇게 하면 

99, [2, 15, 22, 55, 55], 580 과 같이 작업량이 오히려 늘어나 버리는 경우가 생긴다.

따라서, 우선순위 큐를 사용해서 최대 작업량에서 계속해서 -1씩 해주는 방법으로 풀이했다.

 

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

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