[프로그래머스 Level_3 / C++] 최고의 집합

1. 각 원소의 합이 S가 되는 수의 집합
2. 위 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합

원소의 합이 S가 되는 수 중에 제일 곱이 최대가 될 때가 언제인지 짐작이 오면 된다. 

S를 N으로 나누었을 때 생성되는 평균값에 가까울수록 곱이 최대가 된다. 

 

예를 들어,

 

S = 86 이고  N = 9 이고, 이 의미는 숫자 9개를 가지고 합을 86을 만들면 된다. 

 

N으로 S를 일단 나눠보자. 

 

몫은 9 (평균값)이고 나머지는 5이다. 

평균값 9를 N개 만큼 나열 해보자. 

 

"9 9 9 9 9 9 9 9 9"  

 

여기에 나머지 값인 5를 가지고 1씩 공평하게 나눠주자. 

 

"9 9 9 9 10 10 10 10 10"

 

이 값들을 곱했을 때 최대가 나온다. 

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

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

 

코딩테스트 연습 - 최고의 집합