문제 설명
회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.
제한 사항
- works는 길이 1 이상, 20,000 이하인 배열입니다.
- works의 원소는 50000 이하인 자연수입니다.
- n은 1,000,000 이하인 자연수입니다.
풀이
주어진 작업들을 n만큼 뺀 뒤 각 작업 소요일을 제곱한 값을 최소화하는 문제이다.
n개의 수를 빼는데 몇 번째 작업에서 빼는지에 따라 달라지며 이전의 결과를 활용할 수 있다고 생각했다.
그래서 dp로 문제를 풀려했지만 dp에 저장할 값이 야근 지수와 해당 단계에서 가지고 있는 가장 긴 작업 소요일이 필요했다.
그렇기 때문에 자료구조가 지저분해진다.
다시 생각해 보니 몇 개를 빼든 가장 큰 작업 소요일을 빼는 것이 유리하다.
제곱의 값이 야근 지수이기 때문에 이 논리는 항상 올바른 값을 보장한다.
그래서 n번 동안 정렬하여 가장 큰 값을 1씩 줄이면 된다고 생각했다.
for(int i = 0 ; i < n; i++)
{
sort(works.begin(), works.end(), greater<int>());
work[0]--;
}이렇게 구현하면 정확성은 모두 맞지만 효율성에서 시간초과가 걸리게 된다.
따라서, 다른 자료구조를 통해 정렬을 해야 한다.
이때, 유리한 자료구조는 heap이다.
heap을 사용하는 자료구조는 set, map 등 다양하게 있지만 둘 다 이번 문제와는 어울리지 않는다.
이번 문제에서 가장 적절한 자료구조는 priority_queue이다.
pq는 요소가 변경될 때, 자동으로 정렬을 수행한다.
따라서, pq를 이용해 가장 큰 값을 가져와 1을 뺀 뒤 다시 넣어 정렬을 진행한다.
이 과정을 n번한 뒤, 야근지수를 구하면 된다.
전체 코드
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
long long solution(int n, vector<int> works) {
long long answer = 0;
priority_queue<int> pq;
for(auto work : works) pq.push(work);
for(int i = 0 ; i < n; i++)
{
int work = pq.top();
pq.pop();
work--;
pq.push(work);
}
while(!pq.empty())
{
int work = pq.top();
pq.pop();
if(work < 0) continue;
answer += work*work;
}
return answer;
}