Link : Lv3. 최고의 집합
- 문제 설명
자연수 n 개로 이루어진 집합 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.
- 각 원소의 합이 S가 되는 수의 집합
- 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합
예를 들어서 자연수 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 이하의 자연수입니다.
- 문제 풀이
자연수 n 개로 이루어진 집합 중에 합이 s 가 되는 원소들의 최대 곱은
위의 예시 처럼 ({1, 8} 보다 {4, 5} 가 큰 것 처럼) n 으로 나누어진 값에 가까울 수록 최대가 된다.
따라서 s를 n으로 나눈 뒤에 그 값을 기준으로 s를 n으로 나눈 나머지를 하나씩 (+1) 분배 하면 끝이다.
예를들어, 위의 예시를 보면 quota = 9 / 2 = 4, remain = 9 % 2 = 1 가 되며 {4, 5}가 될 것이다.
그런데 오름차순으로 넣어줘야 하므로 n에서 remain을 빼준다. nremain = n – remain;
이렇게 하면, i = 1부터 돌릴 때 if(i > nremain) 일 경우 만 (+1) 을 해주면 오름차순 정렬된다.
효율성은 BigO(n)이 될 것이다.
사실.. 이 문제는 간단한데 초반에는 헤매었다.
문제 예시를 얼핏 보고 중복을 허용하지 않는 듯 하여 처음에 그렇게 풀었더니 그게 아니었다.
예를들어, n = 2이고 s = 6인 경우 중복을 허용하면 {3, 3}이 제일 크고
중복을 허용하지 않는다면 {2, 4}가 제일 크다.
둘 중에는 중복을 허용하는 경우인 3 * 3 = 9 가 2 * 4 = 8 보다 크다.
문제에서 중복을 허용한다고 얘기해 줬으면 더 좋았을 텐데 그 점이 조금 아쉬웠다.
번외로 중복을 허용하지 않는 경우를 구해보면,
집합의 합인 s 는 n 개의 집합의 최소 합보다 커야 한다는 조건이 또 생긴다.
1, 2, 3, 4 ….n 의 합은 n * (n + 1) / 2 이고 이 합이 s를 넘어 버리면
중복을 허용하지 않고 만들 수 없기 때문에 -1을 반환한다.
s가 최소합 보다 크면 s에 최소합을 빼준다.
빼주는 이유는 최소합을 빼줌으로써 기존 배열을 1, 2, 3, 4 … 최소로 끌어 올 수 있기 때문이다.
예를들면, 위의 예시는 {4, 5} 가 답이다. s인 9 에서 최소합인 3을 빼주면 6이 되고
이것을 n인 2를 나누면 quota = 3, remain = 0 이 되며 nremain = 2가 된다.
기본적으로 배열을 {1, 2} 를 최고의 집합으로 가지고 있다고 가정하고 (최소합을 빼줬으므로)
여기에 { 1 + quota, 2 + quota} 을 하면 {4, 5} 가 된다.
이 역시 효율은 BigO(n)이 될 것이다.
Source Code : the_best_set.cpp