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

programmers.co.kr/learn/courses/30/lessons/12927

코딩테스트 연습 - 야근 지수

- 접근법

최종적으로 각 일 크기의 제곱들의 합이 가장이 작게 만들어야 하는 것이 이 문제의 목표이다.야근 1시간 마다 일 크기들중 하나를 -1 할 수 있다. 그렇다면 최종적인 목표의 답을 얻기 위해선 어떻게 해야할까?문제와 예시 데이터들을 보면, 결국 제곱들의 합을 작게 만들기 위해서는 일 크기들 중 큰 값들을 감소시켜야 한다.따라서 이 문제는 그리디를 적용시킬 수 있으며, 결국 야근 1시간 마다 처리해야 할 일의 크기 중 최댓값을 가장 효율적으로 얻는 방법을 고민해야 한다.

 

때문에 나는 우선순위큐(priority_queue> 자료구조를 사용해서 각 시간 마다 최댓값을 얻어 해결하였다.

 

---

- 소스코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
priority_queue<int,vector<int>,less<int> > v_work;
long long solution(int n, vector<int> works) {
    long long answer = 0;
    int must_work;
    for(int i=0;i<works.size();i++) {
        v_work.push(works[i]);
    }
    while(!v_work.empty() && n>0) {
        must_work=v_work.top();
        must_work--;
        n--;
        v_work.pop();
        if(must_work!=0) {
            v_work.push(must_work);
        }
    }
    while(!v_work.empty()) {
        answer+=(long long)(v_work.top()*v_work.top());
        v_work.pop();
    }
    return answer;
}