Programers 야근지수 / C++

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

프로그래머스

 

아이디어

남은 작업량의 제곱이 되기 때문에 최대한 높은 작업량을 최대한 골고루 감소시켜야 합니다

연산마다 vector를 내림차순으로 정렬하는 방법을 생각할 수 있지만,

c++의 sort의 시간복잡도는 N logN, priority_quque의 push, pop 시간 복잡도는 logN으로 priority_queue가 시간복잡도의 우위에 있습니다.

하여 priority_queue를 이용하여 작업량이 큰일 부터 줄여가며 최소 야근지수를 구하면 됩니다.

. 

 

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

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