[Programmers] 야근지수

문제

코드

#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(int i=0; i<works.size(); i++){
       pq.push(works[i]);
    }
    
    for(int i=0; i<n; i++){
        int a =pq.top();
        if(a>0) a--;
        pq.pop();
        pq.push(a);
    }
    
    for(int i=0; i<works.size(); i++){
        cout<<pq.top();
        answer+=pq.top()*pq.top();
        pq.pop();
    }
    return answer;
}

풀이

배열에 있는 수들의 제곱의 합이 최소가 되도록 n값을 소모하여 조정하는 문제이다.

제곱의 합이 최소가 되기 위해서는 각 요소들이 전체합의 평균값에 근접하면 된다.
priority_queue를 이용해서 가지고 있는 수중 가장 큰 수의 값을 -1 하여 업데이트 해주었다.

음수가 되는 경우에는 오히려 제곱의 합이 늘어나게 되므로 if(a>0) 조건을 걸어 필터링 하였다.