최고의 집합 알고리즘

문제 설명

본 문제는 프로그래머스라는 알고리즘 사이트에서 가져온 문제입니다. 알고리즘을 푸는 모든 과정은 자바스크립트로 이뤄졌습니다.

먼저 이 문제는 다음과 같다.

자연수 n 개로 이루어진 집합 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 최고의 집합은 n개의 원소의 합은 S가 되는 수의 집합입니다. 이러한 조건을 만족하며 n개의 수의 곱이 최대가 되는 집합입니다.

예를 들어 각각의 원소 갯수 n을 2라고 가정하고 원소의 합 S를 9라고 가면 하면 경우의 수는 [1, 8], [2,7], [3,6], [4,5] 등으로 총 4개가 될 수 있다. 그 중에서 최고의 집합은 [4,5]인 집합이다. 예시를 하나 더 들어보자. 원소의 갯수 n은 2이라고 가정하고 원소의 합 S를 13이라고 가정하면 경우의 수는 [1,12], [2,11], [3,10], [4,9], [5,8], [6,7] 이다. 6개의 집합 중 최고의 집합은 [6,7]이 해당한다.

문제 해결 방법 유추

위에서의 두가지 공통점으로는 최고의 집합은 두수의 차가 최소일 경우이다 라는 가정을 얻을 수 있다.

그러한 가정은 다음과 같은 방법으로 증명할 수 있다. 간단하게 예시를 들기 위해 n은 2개라고 가정한다. 자연수 a와 b의 합이 S라고 가정했을 때, a와 b의 관계를 구하기 위해 a-b과 a+b를 비교를 한다.

두 값중 a+b의 제곱근이 a-b의 제곱근보다는 큰 값일 테니 전자에서 후자의 값을 빼준다.

두 값을 서로 비교해서 빼면 결국에 다음과 같이 나온다.

우리가 구하고자 하는 ab 값을 구하기 위해 오른쪽과 왼쪽의 값을 4로 나누어 준다.

그렇게 나누고 나면 우리가 원하는 ab의 값이 나오고 다음의 그림과 같이 a-b 의 값이 작을 수록 ab의 값이 커지는 것을 알 수 있다.

결국 이 문제에서 최다의 ab 값을 구하기 위해서는 n개의 수의 차가 적을수록 원하는 최대값을 구할 수 있다.

문제 해결

먼저 n개의 자연수가 n개의 자연수의 합 S 보다 클 경우를 대비하는 방어코드를 추가했다. n개의 자연수의 합이 S보다 작을 경우는 문제에서 주어진 경우와 같이 -1에 해당하는 배열을 반환해준다.

1
2
3
4
5
6
7
8

function solution(n, s) {
  var answer = [];
  if (n > s) {
    return [-1];
  }

  return answer;
}

우리는 합이 S인 서로 차이가 적은 n개의 자연수를 찾는 것이기 때문에 S를 n으로 나누어 준다. 나눈 값을 그대로 넣어주면 소수점이 나온다. 하지만 우리가 구하고자 하는 값은 자연수 이기에 반올림 혹은 내림 등 중 하나를 선택해야 한다. 여기에서 주목할 것은 우리가 구하고자 하는 값은 올림차순으로 이루어진 집합이기 때문에 여기에서는 내림을 선택해준다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

function solution(n, s) {
  var answer = [];
  if (n > s) {
    return [-1];
  }
  for (let i = 0; i < n; i++) {
    // 하나씩 구해서 answer이라는 배열에 넣으면 구해야할 자연수 n개의 갯수는 점점 줄어든다.
    const number = Math.floor(s/(n-i));
    // 구한 값을 answer 배열에 담아준다.
    answer.push(number);
    // 전체의 갯수에서 구한 값을 제외시켜준후, 다시 배열을 시작한다.
    s = s - number;
  }

  return answer;
}

만약 내림차순으로 이루어진 집합을 구하고자 한다면 다음과 같이 구할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13

function solution(n, s) {
  var answer = [];
  if (n > s) {
    return [-1];
  }

  for (let i = 0; i < n; i++) {
    const number = Math.round(s/(n-i));
    answer.push(number);
    s = s - number;
  }
  return answer;
}