[Programmers]최고의 집합

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

---

  각 원소의 합이 s가 되는 n개의 수의 집합 중 모든 원소의 곱이 최대가 되는 집합을 구하는 문제이다. 예를들어 n = 3, s = 8 이라면 답은 [3, 3, 4]이다.

 

1. 문제 해결 방법

  문제는 크게 2가지 방법으로 해결할 수 있다. 첫 번째는 모든 경우의 수를 찾는 것이고 두 번째는 조건에 맞는 답을 바로 찾는 것이다. 후자가 당연히 효율적이므로 조건에 맞는 답을 바로 찾을 수 있는 방법을 찾아보자

 

n = 2, s = 9 -> [1, 8], [2, 7], [3, 6], [4, 5] -> [4, 5]
n = 3, s = 8 -> [1,1,6], [1,2,5], [1,3,4], [2,2,4], [2,3,3] -> [2, 3, 3]

  위 조건과 답을 관찰해보면 각 원소의 차이가 가장 작을 때, 즉 표준편차가 가장 작은 경우가 답이라는 것을 직관적으로 알 수 있다. 이를 수학적으로 증명할 수 있을까?

 

  식을 간단히 하기 위해 n = 2라는 가정하에 각 요소의 합과 차를 제곱하여 빼주었다. 그러면 (합의 제곱 - 차의 제곱)이 4 * 각 요소의 곱과 동일함을 알 수 있다. 이 때 각 요소의 곱. 즉 우항을 크게 하려면 좌항을 크게해야한다. 이 때 뺄셈은 앞의 항이 크고 뒤의 항이 작을 때 결과 값이 커진다. a+b는 S로 일정하므로 a-b가 작게 해야 4ab가 커짐을 알 수 있다.

그외 증명방법 추측

기하평균과 산술평균의 관계

  추측이지만 산술평균과 기하평균을 이용하여 증명할 수도 있을 것 같다. 산술평균은 일반적으로 사람들이 생각하는 평균으로 n개의 숫자를 모두 더한 후 n으로 나눈 값이다. 기하평균은 n개의 숫자를 모두 곱해서 n 제곱근을 취한 값이다. 산술평균은 기하평균보다 항상 크거나 같다는 관계를 갖고있다.

 

  각 원소의 차이가 가장 작기 위해서는 각 요소가 원소의 합인 S를 n등분한 결과와 가까워야할 것이다. 그러나 S가 항상 n으로 나누어 떨어지지 않을 것이다. 이 때는 몫을 만든 후 나머지도 분배한다. 예를 들어 14 % 3 = 4 ... 2이다. 14를 3등분 하면 몫이 4이므로 배열은 [4, 4, 4]가 된다. 그 후 나머지 2를 최대한 공평하게 분배한다. 따라서 답은 [4, 5, 5]가 된다.

 

2. 코드

function solution(n, s) {
  if (s / n < 1) return [-1];

  const answer = [];
  const num = parseInt(s / n); //몫
  const remainder = s % n; //나머지

  for (let i = 0; i < n - remainder; i++) { //몫 분배
    answer.push(num);
  }

  for (let i = 0; i < remainder; i++) { //나머지 분배
    answer.push(num + 1);
  }
  return answer.sort((a, b) => a - b);
}

  코드는 위와 같다. 먼저 분배가 불가능한 경우를 제외시키고, 몫과 나머지를 구하여 배열을 생성한다. 이 때 나머지의 갯수만큼 몫 + 1인 값이 생기므로 위와 같이 몫과 나머지를 따로 배열에 push할 수 있다.

---

증명 출처: https://blog.martinwork.co.kr/theory/2019/01/19/top-group-algorithm.html