문제

문제링크

접근

• 제곱 관련 문제가 나오면 제일 많이 사용하는 개념은, 제곱한 두 수의 합이 가장 작은 경우는 두 수의 차가 가장 작을 때라는 것이다.
• 수학적 증명을 간단하게 설명하자면 a, (a+x) 이렇게 두 수가 있다면, 제곱에서는 x^2은 양수가 되기 때문에 그 값이 최소가 되어야 합이 최소가 된다. 그래서 두 수의 차이가 작아야 제곱의 합도 최소가 된다.
• 위 개념을 이번 문제에 적용하려면, 값들끼리의 차를 최소로 해야한다. 그래서 n번만큼 최대값을 줄여나가는 방식을 채택하였다.
• 우선순위큐를 활용하여 매번 최댓값을 가져왔다.

소스 코드

정답 소스는 아래와 같다!

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        Queue<Integer> q = new PriorityQueue<>(Comparator.reverseOrder());
        for (int work : works) {
            q.add(work);
        }
        
        while (n > 0 && q.peek() != 0) {
            q.add(q.poll() - 1);
            n--;
        }
        
        while (!q.isEmpty() && q.peek() != 0) {
            int num = q.poll();
            answer += (Math.pow(num, 2));
        }
        
        return answer;
    }
}

아래 예시는 지독한 숏코딩을 한 번 노려본 코드이다.

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        Queue<Integer> q = new PriorityQueue<>(Comparator.reverseOrder());
        for (int work : works) q.add(work);
        
        while (n-- > 0 && q.peek() != 0) q.add(q.poll() - 1);
        while (!q.isEmpty() && q.peek() != 0) answer += (Math.pow(q.poll(), 2));
        
        return answer;
    }
}