[C++] 프로그래머스 야근 지수

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

using namespace std;

// 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다
// 높은 순으로 정렬해서 평균을 낮춰야한다.

long long solution(int n, vector<int> works) 
{
    long long answer = 0;
    priority_queue<int> q;
    
    for(int i = 0; i < works.size(); i++)
    {
        q.push(works[i]);
    }
    
    while(n > 0)
    {
        if(q.empty())
        {
            break;
        }
        
        n--;
        int currNum = q.top() - 1;
        q.pop();
        
        if(currNum > 0)
        {
            q.push(currNum);
        }
    }
    
    while(!q.empty())
    {
        int currNum = q.top() * q.top();
        q.pop();
        
        answer += currNum;
    }
    
    
    return answer;
}

 

풀이

1. 우선 순위 큐를 이용하여 가장 높은 값을 계속 뽑아준다.

2. 가장 큰 값을 낮춰주면서 평균 값이 낮아지도록 유도한다.

3. 제곱을 모두 더한 값이 최소가 된다.

 

느낀점

풀이에 필요한 공식 및 필요한 조건들을 캐치하는걸 더 빠르게 해야될 듯하다.

 

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

프로그래머스