최고의 집합

문제의 핵심은 

자연수 n개로 이루어진 집합 중 곱이 가장 높은걸 구해야 하는 문제이다.

예시로 보듯이 9가 있다면 집합중에 {1,8} , {2,7}, {3,6}, {4,5}가 있지만

이것들 중의 곱이 가장 큰 집합은 {4,5}이다.

두 자연수중에 한쪽만 너무 큰 것보다 두 개의 자연수의 차이가 별 로안나야 가장 큰 수가 나온다.

 

그렇다면 균등하게 큰수를 알아오기 위해서는

집합의 원소 개수인 n과 모든 원소들의 합 s를 나누게 되면 균등하게 큰 수들이 나온다.

9/2를 한다면 몫은 4가나오고 나머지는 1 값이 나오게 된다.

그렇다는 것은 4 + 4 + 1 == 4 + 5가 집합의 곱이 가장 큰 집합이 된다.

 

따라서 s% n이 딱 나누어 떨어진다면 그 몫이 n개만큼 들어간 집합이 가장 큰 집합이 되고

딱 나누어 떨어지지 않는다면 나머지들을 1로 쪼개어 집합에 제일 오른쪽부터 1씩 넣어주면 된다.

 

 

다른 예를 들면

라고 했을 때 최고의 집합을 구하기 위해서는

4는  1+ 1+ 1+ 1과 같기 때문에

맨 오른쪽부터 6에다 1을 더해준다.

그러면 {6,7,7,7,7}이 자연수 n개로 이루어진 집합 중 곱이 가장 큰 집합이 된다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) 
{
    std::vector<int> answer;
    
    if(n > s)
    {
        //최고의 집합을 구할 수 없을떄
        answer.push_back(-1);
    }
    else
    {
        //딱나누어 떨어질 경우
        int Quotient  = s/n;    //몫
        int Remainder = s%n;    //나머지
        for(int i = 0; i < n ; i++)
        {
            answer.push_back(Quotient);
        }
        
        //만약 나머지가 있을경우
        if(Remainder != 0)
        {
            for(int k = n-1; Remainder > 0; k-- )
            {
                answer[k]++;
                Remainder--;
            }
        }
    }
    
    return answer;
}