[Programmers] 최고의 집합 (Java)

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

프로그래머스

---

정말 놀랍게도... 일부러 찾은 문제가 아닌데도... 이전에 문제를 잘못 접근해서 엉뚱한 방식으로 풀었는데 그 방식으로 풀면 되는 문제였다.

알고리즘

그리디 알고리즘이다. 곱의 최대는 똑같이 배분하면 나온다. 즉, 10를 3개로 쪼개서 곱할 때 최대는 [3, 3, 4] 일 때이다.

증명

s = k + k + ... + k

이와 같이 균등하게 분배되어 있을 때, 이게 최선이 아니라고 가정해보자.

그렇다면 적어도 어떤 숫자는 조정해야 할 것이다. 어떤 한 원소에서 m 만큼 빼서 다른 원소에 더해보자. 그럼 이렇게 나올 것이다.

s = (k-m) + k + ... + (k+m)

이러면 앞 식에서는 k^2 이었던 것이 (k-m)(k+m) = k^2 - m^2 으로 변하게 된다. 값이 작아졌다.

이 값이 작아졌다는 것은 앞 식의 값이 항상 더 크다는 것이다. 균등하게 분배하는 것이 정답이다.

정답 코드

class Solution {
    public int[] solution(int n, int s) {
        int[] answer = new int[n];
        if (s < n) {
            return new int[] {-1};
        }
        int base = s / n;
        int bigNum = s % n;
        int smallNum = n - bigNum;
        for (int i = 0; i < smallNum; i++) {
            answer[i] = base;
        }
        for (int i = 0; i < bigNum; i++) {
            answer[smallNum+i] = base+1;
        }
        return answer;
    }
}