[알고리즘] 최고의 집합 (프로그래머스 Level3)

코딩테스트 연습 - 최고의 집합

 각 원소의 합이 s가 되는 n개의 원소로 이루어진 중복 집합 중에서 각 원소의 곱이 최댓값이 되는 경우를 찾으라는 문제이다. 수학적으로 생각했을 때 어떤 경우가 최대가 되는지 구하는 건 매우 간단하다.

 

Solution

 만약 s = 8이고 n = 2라고 가정해보자. 나올 수 있는 경우는 아래와 같다.

 

각 원소의 곱	7	12	15	16
케이스	(1, 7)	(2, 6)	(3, 5)	(4, 4)

 보다시피 각 원소들이 s / n에 가까워질수록 원소의 곱이 커진다. 이 원리를 생각해보면 n개의 원소를 s / n으로 채우고 추가적으로 s % n 개만큼의 원소에 1씩 더해주면 원소의 곱이 최대가 되는 경우가 구해진다.

 만약 s = 9, n = 2인 경우라면 (4, 4 + 1) 이 되어서 (4, 5)가 된다. 그리고 배열의 원소는 자연수이므로 0이 올 수 없기 때문에 n > s보다 큰 경우라면 값을 구할 수 없으므로 [-1]을 반환한다.

 

import java.util.Arrays;

class Solution {
	public int[] solution(int n, int s) {
		int[] answer = {};

        //n개의 수로 이루어진 자연수들의 합 s를 만들기 위해선 n은 최대 s까지만 가능함(1의 s개합)
		if(s < n)
		{
			answer = new int[1];
			answer[0] = -1;
		}
		else
		{
			answer = new int[n];

            //합이 s가 되는 집합 중에서 원소가 s/n에 가까울수록 원소들의 곱이 커진다.
			Arrays.fill(answer, s%n, answer.length, s/n);
            
            //나머지는 1씩 원소들에게 공평하게 분배
			Arrays.fill(answer,0, s%n, s/n+1);

			Arrays.sort(answer);
		}

		return answer;
	}
}