레벨2) 최고의 집합

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

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

예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다.
{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }
그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다.

집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요.

제한사항

• 최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 return 해주세요.
• 만약 최고의 집합이 존재하지 않는 경우에 크기가 1인 1차원 배열(list, vector) 에 -1 을 채워서 return 해주세요.
• 자연수의 개수 n은 1 이상 10,000 이하의 자연수입니다.
• 모든 원소들의 합 s는 1 이상, 100,000,000 이하의 자연수입니다.

우선 이 문제를 직관이 아닌 수학적 접근을 통해 증명한 승완이에게 박수를 보낸다...

(차후에 증명을 정리하면 추가해야지..)

이 문제 역시 예산 처럼, 제약조건이 있는 상황에서 최대값을 뽑는 문제이다.

예를 들어 변수가 3개라 할때 x + y + z  = N , xyz = ? 식의 구성이라 라그랑주로 접근할수도 있다(!!!!)

물론 난 그렇게 못한다..

직관적으로 접근해보면 어떤 경우에 가장 클까?

곱한 값이 가장 크려면, 가장 큰 애들끼리 곱하면 된다.

즉, 9를 두개의 수로 나누어서 곱한다고 할때, 제일 큰 수가 나오게 나누면 된다

이 얘기는 9의 평균 값, 4.5 * 4.5로 하면 가장 큰 값이 나온다는 뜻이다.

만약 9을 3개의 수로 나누어서 구해야 한다고 하면 당연히 3, 3, 3이 제일 크다.

(이러한 직관적 접근을 승완이는 수학적으로 접근하여 증명하였다!!!... 라그랑주 or 산술평균과 기하평균을 통해서...)

그렇기 때문에 평균에 가장 근접한 숫자들을 구해서 곱하면 된다.

물론 이렇게만 생각하면 한가지 큰 실수가 발생한다.

(나는 여기서 몫을 구하고 남은 나머지를 그냥 다른 하나의 값에 모두 더했다. 그리고 틀렸따...)

11을 3개의 숫자로 구성한다고 생각해보자.

1) 11을 3으로 나누면 3이 나온다.

2) 3, 3, 3의 총 3개의 숫자와 2가 남는다.

3) 남은 2를 3개중 아무거나에 더하면 3, 3, 5가 된다

4) 정답이 아니다.

왜 3,3,5는 정답이 아닐까? 

(정답은 3,4,4 이다.)

11을 다시 3으로 나눠보자, 자연수가 아닌 실수까지.

그러면 3.6... 이 나온다.

즉 가장 큰 값은 3.6 * 3.6 * 3.6이고 결국 우리가 구하는 값은 이에 가장 가까워야한다.

3, 3, 5

3, 4, 4,

이 두개의 수중 누가 더 3.6, 3.6, 3.6에 가까울까?

후자이다...

나는 위에까지 생각을 못했다...

이러한 사실을 알도 코드를 수정해봤지만 시간초과가 뜬다.. 슬프다