Level 3. 야근 지수

Level 3. 야근 지수

 

 

처음에 문제 지문이 이해가 되지 않았는데 예제를 보니 이해가 됐다.

 

(n - 1)² - (n - 2)² < n² - (n - 1)² 이기 때문에 가능한 큰 수부터 감소시켜야 한다.

• 그렇기에 매번 가장 큰 수를 뽑을 수 있는 우선순위 큐가 효율적이다.

 

작은수부터 큰 수로 나열시킨다면 직각삼각형 모양이 되는데, 횡스크롤 비행기 게임의 느낌처럼 큰 수부터 위에서 아래로 총알을 쏴 줄여나가는 모습이 떠올랐다.

 

n의 값을 1씩 줄여나가는 사람들이 많았는데, 우선순위 큐에서 뽑은 최댓값과 현재 큐에 있는 최댓값을 비교하면 가능한 만큼 한번에 줄일 수 있다.

• 줄일 수 있는 최댓값은 (뽑은 수 - 큐의 최댓값 + 1)이다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

    for (int w : works)
        prQue.emplace(w);

    while (0 < n)
    {
        int num = prQue.top(); prQue.pop();
        int minus = min(n, num - prQue.top() + 1);

        n -= minus;
        prQue.emplace(max(0, num - minus));
    }

    while (!prQue.empty())
    {
        answer += prQue.top() * prQue.top();
        prQue.pop();
    }

    return answer;
}