최고의 집합

문제 정보

• 프로그래머스 Lv.3
• 문제 링크

풀이

합이 S가 되면서, 원소들의 곱이 최대가 되도록 하려면, 원소들 간의 차이가 최소가 되도록 해야 한다.

다르게 표현하자면, S개의 달걀을 n개의 바구니에 최대한 균등하게 나누는 것이다.

그러므로 배열의 각 원소를 $\lfloor \frac{S}{n}\rfloor$ 으로 초기화하고, 나머지(S % N)를 1씩 분배해준다. 이때, 문제에서 오름차순으로 정렬된 배열을 반환하라 했으므로, 배열의 뒤에서부터 1씩 더하면 된다.

추가로, n이 S보다 큰 경우에는 원소가 최소 1 이상인 자연수 집합을 만들 수 없으므로 배열에 -1을 담아 반환한다.

코드

import java.util.*;
 
class Solution {
    public int[] solution(int n, int s) {
        if (n > s)
            return new int[]{ -1 };
        
        int[] answer = new int[n];
        int remainder = s % n;
        
        Arrays.fill(answer, s / n);
        
        int idx = n - 1;
        while (remainder > 0) {
            answer[idx]++;
            remainder--;
            idx--;
        }
        
        return answer;
    }
}