문제

야근을 하면 야근 피로도가 쌓인다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값이다. N시간 동안 야근 피로도를 최소화하도록 일할 것이다. 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성하시오.

입력

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

출력

최소 야근 피로도

예

works = [4, 3, 3] / n = 4인 경우 =>
야근 지수를 최소화하기 위해 4시간동안 일을 한 결과는 [2, 2, 2]이며. 이 때 야근 지수는 2^2 + 2^2 + 2^2 = 12 이다.

works = [2, 1, 2] / n = 1인 경우 =>
야근 지수를 최소화하기 위해 1시간동안 일을 한 결과는 [2, 1, 1]이며. 이 때 야근 지수는 2^2 + 1^2 + 1^2 = 6 이다.

works = [1, 1, 1] / n = 5인 경우 =>
5시간 이내 일을 모두 처리할 수 있으며 이때 결과는 0 이다.

풀이

문제를 요약 하자면, “주어진 n을 분배하여 works에 있는 값을 차감한 값의 제곱값이 최소가 되게 n을 분배한다.” 는 것이다. 여기서 중요한 점은 n을 처리한 남은 works의 값의 제곱값 합을 최소가 해야한다는 점이다.
그러기 위해선 우선으로 처리해야 하는 것은 실시간으로, 가장 큰 작업량을 가진 일을 먼저 소모시켜야 한다는 점이다.

그러기 위해서 작업량이 많은 순으로 우선순위 큐를 만들어서 먼저 줄어드는 것부터 자리를 잡는다. java에서 PriorityQueue는 Integer 기준으로 오름차순으로 정렬되는 거라 역순으로 설정하여 작업량이 높은 일이 먼저 뽑히게 구성한다.

// 최대 작업량 우선순위 큐를 역순으로 설정
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// 작업량을 우선순위 큐에 추가
for (int work : works) {
  maxHeap.add(work);
}

이후 주어진 n시간 동안 1씩 큐에 있는 작업의 작업량을 차감한 뒤 다시 큐에 넣어주는 작업을 한다. 이 작업이 바로 최소화를 하기 위한 작업이 된다.

// n 시간 동안 가장 큰 작업량을 1씩 줄임
for (int i = 0; i < n; i++) {
  if (maxHeap.peek() == null || maxHeap.peek() == 0) {
    break; // 더 이상 줄일 작업량이 없으면 중단
  }
  int maxWork = maxHeap.poll();
  maxHeap.add(maxWork - 1);
}

이후 n시간을 다 쓴 우선순위 큐 작업량의 제곱을 다 합한 값을 구해주면 최소값이 된다.

// 남은 작업량의 제곱의 합을 계산
long answer = 0;
while (!maxHeap.isEmpty()) {
  int work = maxHeap.poll();
  answer += (long) work * work;
}

return answer;

결론

먼저 수학적으로 생각해야 하는 것이 필요하다. 뭐가 최소값이 되는 것일까? 에 대해서부터 시작하는 고민이 필요하다. 각 요소의 제곱의 합이라면 각 요소 중 가장 큰 값을 먼저 줄이는 생각을 할 수 밖에 없다.
그렇다면 이를 어떻게 구현할 것인가에 대하여 고민이 필요하다. 무조건 큰 거 부터라는 생각이면 이제 우선순위란 개념이 들것이고, 거기에 더 나아가 우선순위 큐까지 생각해낼 것이다.
여기까지 생각했다면 거침없이 구현하고 테스트하면 끝이다.
=> 수학적 고민을 구현하는 문제