# 프로그래머스 : 최고의 집합 (Level 4)

[문제]

자연수 N개로 이루어진 집합 중에, 각 원소의 합이 S가 되는 수의 집합은 여러 가지가 존재합니다. 최고의 집합은, 위의 조건을 만족하는 집합 중 각 원소의 곱이 최대가 되는 집합을 의미합니다. 집합 원소의 개수 n과 원소들의 합 s가 주어지면, 최고의 집합을 찾아 원소를 오름차순으로 반환해주는 bestSet 함수를 만들어 보세요. 만약 조건을 만족하는 집합이 없을 때는 배열 맨 앞에 –1을 담아 반환하면 됩니다. 예를 들어 n=3, s=13이면 [4,4,5]가 반환됩니다.
(자바는 집합이 없는 경우 크기가 1인 배열에 -1을 담아 반환해주세요.)

[풀이]

처음 생각한 풀이는 다음과 같았다.

자연수 N개로 이루어져 있는 집합 = 1부터 차례대로 검사
검사 중 연속된 n개의 자연수 합이 s가 되는 경우 확인

문제는 '항상 연속된 수는 아니다!'

이러던 중에 '연속된 수 범위의 반을 기준으로 더해나갔을 때 가장 큰 곱이 나온다'는 것을 확인했다.

예를 들어 연속된 수 4개의 합이 25일 경우,

25/4 = 6 (정수 값만 처리한다고 하자)
6 + 6 + 6 + 7 = 25가 되는데, 이 때의 곱은 1512가 된다.

수학적인 증명으로 왜 이 경우에 가장 큰 곱이 나오는지 확실하게 말은 할 수 없지만(-_-;;)

다른 경우를 곱하다보면 이 경우가 가장 큰 곱이 나오는 것을 확인할 수 있다.

(확실한 것은 6 이상의 수를 처음으로 두고 진행할 경우, 남은 3개를 6보다 큰 수를 넣을 수 없게 된다)

전체 수의 합을 sum, 개수를 n, sum/n = x라고 할 때, 이를 식으로 표현하면

x는 결국 처음 시작 수(기준)가 된다.
결국 x * n은 sum 보다 작거나 같게 되는데, 이러면 계산을 해도해도 종료가 나오지 않는다.
그래서 (x+1)*n을 sum과 비교해야 한다. (어찌되었든 x를 기준으로 두면 최대 x혹은 x+1로 집합이 구성될 것이기 때문이다 - 실제 x를 두고 집합을 구성해보면 안다)

점점 설명이 복잡해지는데, 정리하면

x를 바로 이전 집합의 수라고 할 때,

(x+1)*(남은 개수) > sum - x라면 : x의 크기를 증가하면 바로 전체 합보다 커지기 때문에 그대로 x로 진행
(x+1)*(남은 개수) <= sum - x라면 : x의 크기를 증가해도 전체 합보다 커지지 않기 때문에 앞으로 x+1로 채워 넣으면 된다.

(죄송합니다.. 수학적인 지식보다 감으로 풀어서 설명이...)

코드로 살펴보면,

vector<int> bestSet(int no,int sum)

{

vector<int> answer;

int value = sum/no;

if(value < 1) {

answer.assign(1,-1);

return answer;

}

answer.assign(no, 0);

answer[0] = value;

for(int i=1; i<no; i++) {

if(((value+1)*(no-i)) > sum - answer[i-1]) {

answer[i] = value;

}

else {

answer[i] = value+1;

}

value = answer[i];

sum -= answer[i];

}

return answer;

}

대신 조건에 해당하는 값이 전혀 없을 경우 -1을 출력하라고 했다.

이 경우는 개수만큼 1을 다 더해도 sum이 되지 않는 경우인 sum / n < 1이므로 이 경우만 예외 처리로 두고 진행하면 된다.

Joon's Blog