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

프로그래머스

 

• 집합 내의 숫자들 간의 격차가 적을수록 곱이 최대가 됨
• s를 n으로 나눈 몫이 자연수가 아니면(= s가 n보다 작으면) 합이 s인 집합을 만들 수 없으므로 -1 리턴
• 자연수면 나눈 몫을 n개 저장하고 나머지만큼 각 원소에 1씩 더해줌
• 오름차순 정렬 수행

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

using namespace std;

// 집합 내의 숫자들 간의 격차가 적을수록 곱이 최대가 됨
// s를 n으로 나눈 몫이 자연수가 아니면(= s가 n보다 작으면) 합이 s인 집합을 만들 수 없으므로 -1 리턴
// 자연수면 나눈 몫을 n개 저장하고 나머지만큼 각 원소에 1씩 더해줌
// 오름차순 정렬 수행

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