# 프로그래머스 : 야근 지수 (Level 3)

[문제]

회사원인 수민이는 많은 일이 쌓여 있습니다. 수민이는 야근을 최소화하기 위해 남은 일의 작업량을 숫자로 메기고, 일에 대한 야근 지수를 줄이기로 결정했습니다. 야근 지수는 남은 일의 작업량을 제곱하여 더한 값을 의미합니다. 수민이는 1시간 동안 남은 일 중 하나를 골라 작업량 1만큼 처리할 수 있습니다. 수민이의 퇴근까지 남은 N 시간과 각 일에 대한 작업량이 있을 때, noOvertime 함수를 제작하여 수민이의 야근 지수를 최소화 한 결과를 출력해 주세요. 예를 들어, N=4 일 때, 남은 일의 작업량이 [4, 3, 3] 이라면 야근 지수를 최소화하기 위해 일을 한 결과는 [2, 2, 2]가 되고 야근 지수는 22 + 22 + 22 = 12가 되어 12를 반환해 줍니다.

[풀이]

요즘 한창 Machine Learning 공부에 매진하다보니 알고리즘을 몇 일동안 못했다.
머리 좀 풀어볼까 하고 시작했는데, 한끝차이의 접근 오류로 인해 잠깐 애를 먹었다.

우선 내가 생각한 방식은

1. 행렬이 {4,3,3}이라고 할 때, 행렬의 갯수는 3
2. 줄일 수 있는 시간이 n (예시 에서는 4)라고 할 때,
3. 행렬 원소의 전체 합은 10, 그리고 시간을 모두 쓴 결과 값은 10-n
4. 10-n을 행렬의 갯수 3만큼 나눈 원소 값을 일일이 제곱해준다
5. 만약 나머지가 존재한다면, +1만큼 원소 갯수마다 해주면서 제곱

뭐 대충 이론은 비슷한데, 내가 한가지 생각하지 못한것이 있었다.

"만약 10-n을 행렬의 갯수 3만큼 나눈 결과 값이 2인데, 어떤 원소에는 1만 존재한다면?"

그래서 조금 다른 방식으로 접근을 하였는데,

"행렬 전체에서의 최대 값을 먼저 하나씩 빼주면서 전체 원소 값의 평균값을 맞춰주는 것"

결국 생각하는 방식은 비슷한데, 접근이 조금 다르다고 할까나(나는 그렇게 생각한다)

소스는 다음과 같다.

int noOvertime(int no,vector<int> works)

{

    int answer = 0;

    for(int i=0; i<no; i++) {

        sort(works.begin(), works.end(), greater<int>());

        works[0] -= 1;

    }

    for(int i=0; i<works.size(); i++) {

        answer += works[i] * works[i];

    }

    return answer;

}

계속 소팅을 하는 오버헤드가 들 것 같기는 한데, 더 좋은 방법을 생각하지는 못했다.

역시 알고리즘은 무조건 '꾸준하게' 공부해야하는 것 같다.