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

 

 

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

 

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

프로그래머스

---

 

 

해결방안

 

우선순위 큐 priority_queue

힙 Heap

 

 

이 문제의 핵심은 "작업량을 최대한 균등하게 줄여서 남은 작업량의 제곱 합을 최소화하는 것"이다.

 

• 남은 작업량을 최대한 균등하게 줄여야 한다.
• 최대 힙을 사용해 현재 가장 작업량이 많은 일을 1만큼 줄이고, 다시 힙에 넣는 과정을 반복한다.
• 이렇게 하면 작업량이 많은 일부터 줄어들게 되고, 전체 작업량이 균등하게 분배된다.
• 정리해서 다시 말하면, 가장 큰 작업량을 줄이면서 남은 작업량의 제곱 합을 최소화 했다.

---

 

 

정답 코드

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;

long long solution(int n, vector<int> works) {
    long long answer = 0;

    priority_queue<int> pQ; // 최대 힙을 이용해 작업량이 많은 순서대로 처리

    int total = 0; // 전체 작업량
    for(int i = 0; i < works.size(); i++){
        total += works[i];
        pQ.push(works[i]); // 최대 힙에 작업량을 추가
    }

    if (total <= n) return 0; // 남은 작업량이 소진할 수 있는 야근 시간보다 적거나 같으면 피로도는 0


    while (!pQ.empty() && n > 0) { // 힙이 비어있지 않고 n이 0보다 클 때까지 반복
        int top = pQ.top(); // 최대 작업량을 가져옴
        pQ.pop(); 			// 최대 작업량을 힙에서 제거

        n--; 				// 야근 시간 1시간 소진
        top--; 				// 최대 작업량 1시간 소진
        pQ.push(top);   	// 줄어든 작업량을 다시 힙에 추가
    }

    while(!pQ.empty()) {
        int top = pQ.top();
        pQ.pop(); 			

        answer += pow(top, 2); // 작업량의 제곱을 더해서 피로도를 계산
    }

    return answer; // 최종 피로도를 반환
}

int main(){
    cout << solution(4, { 4, 3, 3 }) << "\n";
    cout << solution(1, { 2, 1, 2 }) << "\n"; 
    cout << solution(3, { 1, 1 }) << "\n"; 

    return 0;
}

 

 

---