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

풀이)

제곱들의 합이 최소여야 한다. -> 큰 숫자일수록 제곱하면 크기가 엄청 커지므로, 큰 work원소부터 줄여준다. 

큰 원소부터 1씩 줄여주기 위해 Priority queue를 사용했다.

PQ는 내림차순으로 정렬되므로 n번만큼 PQ의 top을 pop한 후, 값을 1 줄인 후 다시 PQ에 넣는 과정을 반복하면 된다. 

만일 n번만큼 하기도 전에 모든 work원소가 0이면 야근을 할 필요 없다는 뜻이므로 바로 0을 return한다.

코드)

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

long long solution(int n, vector<int> works) {
    long long answer = 0;
    priority_queue <int> qu;
    for(int i=0;i<works.size();i++){
        qu.push(works[i]);
    }
    while(n--){
        int temp = qu.top();
        if(temp ==0) break;
        qu.pop();
        temp--;
        qu.push(temp);
    }
    if(n>0) return 0;
    else{
        while(!qu.empty()){
            int temp = qu.top();
            if(temp ==0) break;
            qu.pop();
            answer += temp*temp;
        }   
    }
    return answer;
}