[프로그래머스] 최고의 집합

작성일: 2024-12-14

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

접근 방식

모든 집합을 구할 필요가 없다.

이 문제의 핵심은, 집합의 원소들이 중앙 값에 근접할 수록 각 원소의 곱이 최대가 된다는 것이다.

예제를 살펴보면, 9를 만들 수 있는 집합은 {1, 8}, {2, 7}, {3, 6}, {4, 5}가 있다. 이 중에서 각 원소의 곱이 최대인 것은 마지막인 {4, 5}이다.

이와 관련된 수학의 부등식이 존재한다. 바로 산술-기하 평균 부등식이다.

앞서 말했던, 이론을 증명하는 내용을 담고 있다.

나도 위의 부등식은 알지 못했지만, 예제를 살펴보고 테스트 케이스를 작성하던 과정에서 법칙을 깨닫게 되었다.

ex) s=3, n=16일 때, 최고의 집합은 {5, 5, 6} 이다

ex) s=2, n=8일 때, 최고의 집합은 {4, 4} 이다

결과

소스 코드

import java.util.*;

class Solution {
    public int[] solution(int n, int s) {
        // 예외 처리
        if (s < n) {
            return new int[] {-1};
        }

        // 기본 몫과 나머지 계산
        int num = s / n;
        int remain = s % n;

        // 정답 배열 초기화
        int[] answer = new int[n];
        Arrays.fill(answer, num); // 모든 원소를 기본 몫으로 채움

        // 나머지 만큼 뒤에서부터 +1씩 분배
        for (int i = 0; i < remain; i++) {
            answer[n - 1 - i] += 1;
        }

        return answer;
    }
}

모든 원소가 비교적 균등해야 한다.

중복을 허용하기 때문에, s가 n으로 나누어 떨어지면, 몫이 정답이 되고

나누어 떨어지지 않는다면, 몫으로 전부 분배하되, 뒤에서부터 하나씩 1을 더해서 값을 수정하면 된다.