[programmers] 최고의 집합

https://school.programmers.co.kr/learn/courses/30/lessons/12938

프로그래머스

 

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

math

 

---------------------------------------------------풀이----------------------------------------------------

 

곱이 가장 크려면, 합을 가장 비슷한(차가 최소가 되는) 숫자들로 나누어야 한다.

 

예를 들어 9를 2개로 나눈다면,

9 = 1+8 = 2+7 = 3+6 = 4+5 로 나눌 수 있는데,

여기서 곱이 가장 크려면 차가 1이 되는 4,5를 선택해야 한다.

 

9를 3개로 나눈다면,

위 식을 그대로 다시 적용해서 풀 수 있다.

9 = 1+8 = 1+(1+7) = 1+(2+6) = ... = 1+(4+4)

9 = 2+7 = 2+(1+6) = 2+(2+5) = ... = 2+(3+4)

...

이런식으로 적용 가능하다.

여기서는 3,3,3을 선택해야 한다.

 

따라서 합 s를 n으로 나누어 동등한 값을 가진 상태에서, 남은 값을 적절히 분배하는 것이 최대를 만드는 방법이라고 생각하였다.

s가 10, n이 4이라면,

s/n = 10/4 = 2이고, s%n = 10%4 = 2이므로

{2 2 2 2}에서

{2 2 (2+1) (2+1)}로 만들어 주는것이다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> answer;

// 집합의 원소 개수 n, 합 s
void find_max_mul(int n, int s){
    // 서로의 차이가 가장 작을수록 곱이 크다! 즉, 4= 2*2, 8 = 2*2*2 등
    int avg = s/n;
    int left = s%n;
    if(avg == 0){
        answer.push_back(-1);
        return;
    }
    for(int i = 0; i < n - left; i++){
        answer.push_back(avg);
    }
    for(int i = 0; i < left; i++){
        answer.push_back(avg+1);
    }
}

// 자연수 n개. 중복집합. 1<=n<=10000
// 최고의 집합 : 각 원소의 합이 S, 각 원소의 곱이 최대. 1<=s<=100'000'000
// 오름차순으로 정렬된 1차원 배열로 리턴. 없으면 -1을 넣어 리턴.
vector<int> solution(int n, int s) {
    // mul[n] = max(mul[1]*mul[n-1], mul[2]*mul[n-2], ..., mul[n/2]*mul[n/2]) = n에 대한 최댓값
    find_max_mul(n, s);
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

 

처음에는 보자마자 dp를 응용한 dfs가 떠올랐지만,

몇 번 예시를 들어보니, 그럴 필요가 없다는 것을 알게 되었다.

수학적으로 증명한 것은 아니지만, 그냥..그렇다는 것을 본능적으로 깨우친....