[연습문제] 최고의 집합

int 타입의 n과 s가 주어지는데, n개의 수로 집합을 구성하여 모든 원소의 합이 s이고 모든 원소의 곱이 가장 큰 집합을 찾아내는 문제이다. 찾을 수 없다면 -1을 반환한다.

n개의 수를 모두 사용해야 하기 때문에 찾을 수 없는 경우는 n이 s보다 큰 경우를 말한다. 각 원소는 자연수이여야 하기 때문에 s가 3이고 n이 5면 제일 작은 수 1로 구성하더라도 3을 넘기 때문에 불가능하다.

그리고 3, 3처럼 s와 n이 같다면 가장 작은 수 1로 구성해야 하므로 1을 n개만큼 만들어 반환하면 된다.

만약 s가 n으로 나누어 떨어진다면 n개의 수를 s/n으로 구성하면 된다.

그밖의 경우 s가 n으로 나누어 떨어지지 않는다면, 우선 s를 n으로 나눈다. 만약 예제의 9를 2로 나눈다면 몫은 4가 되고 나머지는 1이 된다. 이말은 2개의 4와 나머지 1을 더하면 s를 만들 수 있다는 말이다.

따라서 우선 n개의 몫으로 집합을 구성한다. 그러면 위의 경우 {4, 4}가 되는 데 여기서 나머지를 1씩 각 원소에 분배한다. 여기선 나머지가 1이기 때문에 원소 하나에 1을 주면 끝난다.

만약 s가 11이고 n이 3인 경우, 몫은 3이며 나머지는 2이다. 이 경우 {3, 3, 3}가 베이스 집합이 되고 여기서 나머지 2를 1씩 분배하면 {4,4,3}가 된다. 이를 오름차순 정렬해서 반환하면 되는데 굳이 정렬할 필요없이 1씩 분배할 때 앞에서부터가 아닌 뒤에서부터 분배하도록 하면 정렬을 하지 않아도 된다.   

 

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

using namespace std;

vector<int> solution(int n, int s) {
    if(s < n)
        return {-1};

    if(s == n)
        return vector<int>(n, 1);
    
    // ex) 만약 s%n == 0이라면
    // 몫을 n개 반환
    if(s % n == 0)
        return vector<int>(n, s/n);
    
    // s를 n으로 나눈다.
    int num = s / n;
    int mod = s % n;
    
    // num을 n개 설정하고
    // {num, num, num, ...}
    vector<int> ans(n, num);
    
    // 각 num에 1씩 더한다
    int idx = n - 1;
    for(int i = 0; i < mod; ++i)
    {
        ans[idx--] += 1;
        if(idx == -1)
            idx = n - 1;
    }
    
    return ans;
}