[Programmers] Level 3 : 최고의 집합

프로그래머스

n개의 숫자를 전부 더했을때, s가 되면서 이 값을 모두 곱했을때 최댓값이 되는 집합을 찾으라고 한다. 우선 {-1}을 return 하는 케이스는 정말 간단하다. n이 s보다 크면 절대 정답을 구할 수 없고 반대로 n이 s보다 작거나 같으면 정답은 무조건 존재하게 된다.

그러면, 어떻게 집합을 구할 수 있을까? 브루트 포스를 돌릴 수는 없어 보이는데.. 그래서 그리디하게 생각을 해보자.

예를들어 n = 2, s = 16이 들어왔다고 가정을 해보자.
이때 중복된 경우를 제외하고 가능한 후보의 수는 {1, 15}, {2, 14} ... {8, 8}가 있다. 그리고 최댓값은 8 * 8 = 64이므로 {8, 8}을 return 해주면 된다.

 

이 케이스를 통해 알 수 있는 것은 모든 숫자가 최대한 비슷한 값일때 곱한 값이 최대라는 것을 알 수 있다.
따라서 정답은 무조건 {x, x, x, x+1} 이런식으로 나오게 된다. x는 (s/n)이 들어가면 되고 (s%n) 개만큼 x+1이 들어가면 된다는 것을 알 수 있다. 이를 구현하면 정답이다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(int n, int s) {
    vector<int> answer;
    if (n > s) return {-1};
    for(int i=0; i<n; i++) answer.push_back(s/n);
    for(int i=0; i<s%n; i++) answer[i]++;
    sort(answer.begin(), answer.end());
    return answer;
}

근데 이게 어떻게 가능할까? 증명을 해보자.

// n = 2, s = z
x + y = z

n이 2고, s = z라고 가정하고, x + y = z인 x, y를 선정했다고 가정해보자

maxi = x*y

우리가 구하고 싶은 값은 xy이므로, xy를 maxi라는 변수로 선언해줬다.

x^2 + 2maxi + y^2 = z^2

x + y = z 양쪽에 제곱 연산을 하고, xy에 maxi를 대입한 결과는 위와같다. 우리는 maxi를 구해야 하니깐, maxi만 남기고 전부 넘겨주자.

2maxi = z^2 - (x^2 + y^2)

여기서 양쪽에 2maxi를 더해주자.

4maxi = z^2 - (x^2 + y^2) + 2maxi

그러면 아래와 같이 식을 변경할 수 있다.

maxi = (z^2 - (x-y)^2) / 4

우리는 이제 이 식에서 maxi의 최댓값을 구해야 한다. z와 4는 고정된 값이므로 연산에 아무 영향도 주지 않고, (x-y)^2이 maxi를 결정하는데 영향을 준다.

근데 (x-y)^2는 무조건 양수니깐, 최댓값을 구하려면 (x-y)^2를 최대한 작게 만들어야 한다. 따라서 x와 y의 차이를 최대한 작게 만들었을때 maxi가 커진다는 것을 알 수 있고, 모든 값들이 최대한 인접한 숫자일때 최댓값이 나온다는 것을 알 수 있다.