Programmers - 야근 지수

---

title: Programmers - 야근 지수
date: 2022-08-28
tags:

• Algorithm

---

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

문제 요약

해야 하는 일과 최대 할 수 있는 일의 양이 주어진다.
야근 지수는 남은 일 각각의 제곱의 합이다. 최소 야근 지수를 return한다.

문제 풀이

제곱을 하므로 가장 큰 수부터 1씩 빼는 방식으로 해결할 수 있다.
가장 큰 수를 빼는 이유는 아래 수식을 통해 증명할 수 있다.

Formula

priority_queue를 이용하여 큰 수를 꺼내 1을 빼고 다시 집어넣는 작업을 n번 반복하면 된다.


정확성 테스트에서 최대 약 0.1ms, 효율성 테스트에서 최대 약 30.2ms의 성능을 확인할 수 있었다.
works를 정렬하여 높이가 큰 부분을 통째로 자르는 방식으로 구현하면 더 좋은 성능을 얻을 수 있다.

프로그램

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

using std :: vector ;
using std :: priority_queue ;

long long solution ( int n , vector < int > works )
{
    long long answer = 0 ;
    int iWorkSize = works.size () ;
    int iCount = 0 ;
    priority_queue < int > pqWork ;



    for ( int i = 0 ; i < iWorkSize ; ++i )
    {
        pqWork.emplace ( works [ i ] ) ;
    }
    while ( iCount < n )
    {
        int iWork = pqWork.top () ;
        pqWork.pop () ;

        if ( 0 == iWork )
            return 0 ;

        pqWork.emplace ( iWork - 1 ) ;

        ++ iCount ;
    }
    while ( ! pqWork.empty () )
    {
        int iWork = pqWork.top () ;
        pqWork.pop () ;

        answer += ( long long ) iWork * iWork ;
    }


    return answer ;
}