[Algorithm] Programmers :: 야근 지수

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

프로그래머스

struct Node
{
    int num;
};
 
struct cmp
{
    bool operator() (const Node& a, const Node& b)
    {
        return a.num < b.num;
    }
};
 
long long solution(int n, vector<int> works)
{
    long long answer = 0;
    long long sum = 0;
 
    for (int i = 0; i < works.size(); ++i)
    {
        sum += works[i];
    }
 
    if (sum <= n) return 0;
 
    priority_queue<Node, vector<Node>, cmp> pq;
 
    for (int i = 0; i < works.size(); ++i)
    {
        pq.push({ works[i] });
    }
 
    while (n > 0)
    {
        --n;
        int temp = pq.top().num;
        pq.pop();
 
        if (temp-1 == 0) continue;
 
        pq.push({ temp-1 });
    }
 
    while (!pq.empty())
    {
        answer += pq.top().num * pq.top().num;
        pq.pop();
    }
    
    int asdf = 0;
    return answer;
}

 

역대 푼 3레벨 짜리 중 가장 최단시간에 풀지 않았나...라고 생각하는 문제다.

이 문제는 각 원소의 제곱을 더했을 때 어떤 경우에 가장 값이 낮은가?를 생각해야 하는데,

일단 허용되는한, 반드시 제일 큰값에서 하나씩 빼야 한다.

제곱이기 때문에 다른 곳에서 아무리 커버치려고 해도 제일 큰 수의 제곱만큼 값을 커버칠 수 없다.

 

그렇기 때문에 우선순위큐를 활용해서 잔여시간이 제일 많은 값을 top으로 오게 하여, n번만큼 값을 1씩 빼주고 다시 큐에 넣어주는 작업을 했다.

이 과정을 통해 각각의 각들이 평균값을 향하여 평탄화작업이 되기 때문에 최소의 값을 구할 수 있다.