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

 

 

문제

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

 

야근을 하면 피로도가 쌓이는데 이때 야근 피로도는 야근을 시작한 시점에서  남은 일의 작업량을 제곱해서 더한 값과 같다.N시간 동안 야근 피로도를 최소화 하도록 일을 한다.

 

1시간 동안 작업량을 1만큼 처리할 수 있다고 할 때, 퇴근까지 남은 N시간과 각 일에 대한 작업량 works가 주어지면 야근 피로도를 최소화한 값을 return하면 된다.

 

 

 

입출력 예

 

works	n	result
[4, 3, 3]	4	12
[2, 1, 2]	1	6
[1,1]	3	0

 

 

제한

 

• works는 길이 1 이상, 20,000 이하인 배열입니다.
• works의 원소는 50000 이하인 자연수입니다.
• n은 1,000,000 이하인 자연수입니다.

 

풀이

 

일단 기본적으로 알아야 할 사실은 최소값을 구하기 위해서는 가장 야근량이 많은 수를 줄여야 한다는 사실이다.

 

예를 들어 야근량이 6인 일에서 1시간 동안 일을 해 5로 만드는 것과 야근량이 16인 일에서 1시간 동안 일을 해 야근량을 15로 만드는 것을 비교해 보자.

 

그러면 야근량이 16인 일을 15로 만드는 것이 야근 피로도를 줄이는데 더 효과적임을 알 수 있다. 이는 단순히 제곱식으로 표현해도 알 수 있다. 

$$ (a-1)^2 = a^2 -2a+1 $$

을 보면 1을 뺄 때 마다 2a 만큼 야근 피로도가 줄기 때문에 a의 값 즉, 야근량이 많은 일에서 야근을 해야 야근 피로도를 줄일 수 있음을 알 수 있다.

 

처음에는 가장 많은 야근작업량을 가진 일을 벡터를 이용해 정렬하고 삽입, 삭제 하면서 풀려고 했다.

 

하지만 데이터의 제한이 크지 않아 vector 대신 배열로 바로 계산하기로 했다.

 

worksCnt의 크기를 50001로 선언하고 야근 작업량에 따라 해당 야근 작업량을 가진 작업들이 얼마나 있는지 개수를 셌다.

 

그리고 가장 야근 작업량이 많은 일들을 미리 일을 해 야근 작업량의 max를 조금씩 줄여나가도록 코드를 짰다.

 

아래 그림을 보면 더 이해가 쉬울 것이다.

이처럼 n에서 작업한 양 만큼 줄여주고 max의 값을 가진 작업량을 max-1로 줄이면서 n이 0이되거나 야근 작업량의 최대값이 0이 될 때 까지 반복해 풀었다.

 

[풀이 요약]

1. 야근 작업량에 따라 해야하는 일의 수들을 worksCnt 배열에 저장한다.

2. 야근 작업량 중 작업량이 가장 많은 것을 구한다.

3. 야근 작업량이 많은 것을 기준으로 최대 작업량을 1씩 줄여가며 n이 0이 될 때 까지 반복한다. (또는 최대작업량이 0)

4. n이 0이 되면, 남아있는 일들에 대한 야근 피로도를 구한다.

 

 

Code

 

 

#include <string>
#include <vector>
using namespace std;

long long solution(int n, vector<int> works) {
    long long answer = 0;
    int maxNum=0;
    int worksCnt[50001]={0,};
    for (int i=0; i<works.size(); i++)
    {
        if (maxNum<works[i])
        {
            maxNum=works[i];
        }
        worksCnt[works[i]]+=1;
    }    
    while (n>0&&maxNum>0)
    {
        if (worksCnt[maxNum]<=n)
        {
            n-=worksCnt[maxNum];
            worksCnt[maxNum-1]+=worksCnt[maxNum];
            worksCnt[maxNum]=0;
            maxNum-=1;            
        }
        else
        {
            worksCnt[maxNum-1]+=n;
            worksCnt[maxNum]-=n;
            n=0;
        }
    }
    for (int i=0; i<=maxNum; i++)
    {
        answer+=worksCnt[i]*(i*i);
    }    
    return answer;
}

 

---

 

 

문제는 어렵지 않은데 오랜만에 문제를 풀어서 그런가 STL이 안 익숙하네;;