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

해설

n만큼의 시간을 이용해서 n만큼의 작업을 할 때, 남은 작업들의 제곱 합을 최소로 만드는 문제이다.

현재 남아있는 작업 중에서 가장 값이 큰 작업을 먼저 줄여야 제곱의 합을 최소로 만들 수 있다.

우선순위큐를 이용하여 현재 남아있는 작업들 중 가장 큰 값을 뽑고, 해당 값을 1로 줄여 다시 우선순위큐에 넣는다.

이를 n만큼 반복하면, 제곱합을 최소로 할 수 있는 남아있는 작업 배열이 완성된다.

 

남아있는 작업 배열에서 각 원소를 제곱하여 더한 후 리턴하면 정답이다.

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

long long solution(int n, vector<int> works) {
    
    priority_queue<int, vector<int>, less<int>> pq;
    for (auto x : works) pq.push(x);
    
    for (int i=0; i<n; i++) {
        if (pq.empty()) continue;
        int cur = pq.top();
        pq.pop();
        if (--cur) pq.push(cur);
    }
    
    long long ans = 0;
    while (!pq.empty()) {
        long long cur = pq.top();
        pq.pop();
        ans += cur*cur;
    }
    return ans;
}