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

이 문제를 처음 봤을 때 우선순위 큐가 떠올라야 한다. 

 

야근 피로도를 최소화 하는 그리디한 방법은 눈에 보이는대로 제곱한 수를 최소화 시켜야 한다.  

즉, 숫자 간에 오차가 최대한 작게 만들어야한다. 

 

예를 들어 " 3, 3, 5 " 가 주어졌을 때, 2시간의 시간이 주어지면 

 

"3, 3, 3" 으로 만들어야 제곱의 합이 제일 작고 "1, 3, 5" 로 만들면 제곱의 합이 크다는 것을 알 수 있다.

 

그러므로, 우선순위 큐를 활용해서 존재하는 작업 중 가장 큰 값이 top인 max heap 으로 구성하여

N시간 동안 top에 위치한 작업량을 잠깐 꺼집어내서 한시간씩 빼주고 다시 push 해준다. 

 

#include <string>
#include <vector>
#include <queue>
using namespace std;
long long solution(int n, vector<int> works) {
    long long answer = 0;
    priority_queue <int> q; 
    int number; 
    for(auto x : works)q.push(x); 
    while(n--&&!q.empty()){
        number = q.top();
        q.pop(); 
        if(number!=1)q.push(number-1);
    }
    while(!q.empty()){
        answer+=(q.top()*q.top()); 
        q.pop(); 
    }        
    return answer;
}

 

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