[프로그래머스] 최고의 집합 (C++)

문제

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

아이디어1

산술 기하

${{a_1 + a_2 + \dots + a_n}\over {n}} \geq (a_1 a_2 \dots a_n)^{1\over n}$ (단, 등호는 $a_1 = a_2 = \dots = a_n$일 때만 성립)

• n개의 원소에 대해 합이 s가 되는 수 중 각 원소들의 곱이 최대가 되는 집합
• ${a_1 + a_2 + \dots + a_n} = s$
• $a_1 a_2 \dots a_n = m$
  
  
• 즉, $m$이 최대 $M$이 되기 위해선 $a_i = {s \over n}$이 되어야 함
• 하지만 $a_i$들은 자연수이어야 함
  
  
• $q$는 $s$를 $n$으로 나눴을 때의 몫
• $r$은 $s$를 $n$으로 나눴을 때의 나머지
• $M = q^{n-r} * (q+1)^r$
  
  
• 더 자세한 내용은 생략

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) {
    vector<int> answer;
    
    if (n > s)
        return { -1 };
    
    int q = s / n;
    int r = s % n;
    
    answer = vector<int>(n - r, q);
    answer.resize(n, q + 1);        
    
    return answer;
}