프로그래머스 Lv3 야근 지수

---

접근법

야근 지수를 구하는 공식이 a^2 + b^2 + c^2 .... n^2이므로 수학적으로 접근하면 크기가 균등하게 작아지면 된다는 점으로 접근하면 된다. 따라서 우선순위 큐를 사용해서 현재 가장 큰 값을 줄이는 방식으로 접근하면 된다!

---

풀이

우선순위 큐를 사용하면 제일 큰 값이 top()에 오기 때문에 감소 시킨다. 이 때 N시간 동안 일을 할 수 있기 때문에 N을 감소시키고 우선순위 큐도 갱신하기 위해 pop() 을 진행 후 push()를 해준다. works의 원소가 모두 0이 되는 경우가 있기 때문에 push() 전에 원소가 0인지 아닌지를 체크한다. 

 

works의 모든 원소가 0이되는 예)

works	n	result
[1,1]	3	0

---

코드

#include <string>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

long long solution(int n, vector<int> works) {
    long long answer = 0;
    priority_queue<int> pq;
    
    for(auto work : works) pq.push(work);
    
    while(n != 0 && !pq.empty())
    {
        int work = pq.top();
        pq.pop();
        --n;
        --work;
        if(work)
            pq.push(work);
    }
    
    while(!pq.empty())
    {
        answer += pow(pq.top(), 2);
        pq.pop();
    }
    return answer;
}