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

programmers.co.kr/learn/courses/30/lessons/12938

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

곱이 최대가 나오기 위해서 집합 원소들간의 차이가 최소가 되어야 합니다. 따라서 연산을 줄이기 위해서, 먼저 합s와 원소 개수n을 나눈 몫으로 집합을 채웁니다. 그래서 만약 s % n이 0이 아니라면, 집합 원소들간의 차이를 최소로 만들기 위해서 n-1번째 원소부터 나머지 크기만큼 1씩 더하면 최고의 집합을 만들 수 있습니다.

 

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

vector<int> solution(int n, int s) {
    vector<int> answer;
    // n개로 합이 s인 집합을 만들 수 없는 경우
    if(n > s) {
        answer.push_back(-1);
        return answer;
    }
    
    // 연산을 줄이기 위해 나머지 연산의 몫을 미리 할당
    answer.assign(n, s / n);
    int rest = s % n;
    int pos = n - 1;
    
    // 남은 나머지 크기만큼 뒤에서부터 1씩 더해준다. (집합 원소들 간의 값 차이를 최소화)
    if(rest != 0) {
        while(rest--) {
            answer[pos--]++;
        }
    }
    
    return answer;
}