최고의 집합

문제

자연수 n개로 이루어진 집합 중에 다음 두 조건을 만족하는 집합을 '최고의 집합'이라고 합니다.

1. 각 원소의 합이 S가 되는 수의 집합
2. 위 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합

집합의 원소의 개수 n과 모든 원소들의 합 s가 주어질 때, 최고의 집합을 오름차순으로 정렬하여 반환하는 프로그램을 작성하는 문제입니다. 만약 최고의 집합이 존재하지 않는다면 크기가 1인 배열에 -1을 담아 반환해야 합니다.

• 입력: 자연수의 개수 n (1 ≤ n ≤ 10,000), 모든 원소들의 합 s (1 ≤ s ≤ 100,000,000)
• 출력: 조건을 만족하는 최고의 집합을 오름차순 정렬된 1차원 배열로 반환

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

풀이: 수학적 원리(편차 최소화)를 활용한 분배

합이 일정한 수들의 곱이 최대가 되려면, 수들 간의 차이(편차)가 가장 작아야 합니다. 즉, 모든 수를 최대한 균등하게 나누어 가지는 것이 핵심입니다.

• 예외 처리 (불가능한 경우): 자연수는 최소 1 이상의 값을 가집니다. 따라서 자연수 n개의 합은 최소 n이 되어야 합니다. 만약 n > s라면 자연수만으로 합 s를 만드는 것 자체가 불가능하므로 -1을 반환합니다.
• 기본값 분배: 합 s를 원소의 개수 n으로 나눈 몫(s / n)을 모든 원소에 기본적으로 할당합니다. 이렇게 하면 편차가 0인 상태에서 합을 최대한 s에 가깝게 맞출 수 있습니다.
• 나머지 분배 및 오름차순 정렬: s를 n으로 나누고 남은 나머지(s % n)는 1씩 쪼개어 일부 원소들에게 더해주어야 합니다. 문제에서 오름차순으로 정렬된 배열을 요구하므로, 배열의 뒷부분(즉, 인덱스가 n - 나머지 이상인 부분)에 1씩 더해주면 별도의 정렬 과정 없이 자연스럽게 오름차순 배치가 완성됩니다.

코드

class Solution {
    public int[] solution(int n, int s) {
        // 1. 최고의 집합이 존재할 수 없는 경우 예외 처리
        if (n > s) {
            return new int[]{-1};
        }
        
        int[] ans = new int[n];
        int tmp = s % n; // 나머지
        
        for (int i = 0; i < n; i++) {
            // 2. 모든 원소에 기본 몫을 균등하게 분배
            ans[i] = s / n;
            
            // 3. 나머지만큼 뒤에서부터 1씩 추가하여 오름차순 정렬 상태 유지
            if (i >= n - tmp) {
                ans[i]++;
            }
        }
        
        return ans;
    }
}

알고리즘 분류

수학 (Mathematics), 탐욕법 (Greedy)