프로그래머스 - 최고의 집합 (C++)

 

n개의 자연수를 더해서, s가 될 수 있는 자연수 집합 중에서 원소들의 곱이 가장 큰 집합을 구하면 된다.

 

문제 풀이

이 문제는 어렵게 생각하면 매우 어렵지만 쉽게 생각하면 매우 쉽다.

결론부터 말하면, 최고의 집합은 원소들간의 편차가 가장 작은 집합이다.

 

예를 들어, n이 3이고 s가 10이라고 한다면 최고의 집합은 {3, 3, 4}가 된다.

n이 5이고 s가 40이라고 한다면, {8, 8, 8, 8, 8} 이 된다.

n이 4이고, s가 35라고 한다면 {8, 9, 9, 9}가 된다.

 

왜 그렇게 되는지는 사실 수학적인 증명까지는 잘 모르지만, 직접 몇 가지 경우에 대해 계산해본 결과 위처럼 편차가 가장 고른 숫자 집합이 최고의 집합이 된다는 것을 확인해볼 수 있었다.

 

그렇다면, n과 s를 사용해서 편차가 가장 고른 숫자 집합을 만들면 된다는 것이다.

어떻게 만들면 될까?

 

1. n개 만큼의 원소를 저장할 수 있는 배열을 만든다.

2. 배열의 각 원소를 s / n 으로 저장한다.

3. 배열의 가장 마지막 원소부터 (s % n) 개만큼 앞에 있는 원소까지 1씩 더해준다.

 

위의 과정을 거치면 최고의 집합을 구할 수 있다.

가장 값이 고른 숫자 집합을 만들려면, 당연히 n으로 s를 나누면 된다.

하지만 모든 숫자의 합이 s가 되기 위해선, 나머지가 0이어야만 한다. 하지만, 항상 나머지가 0이되는 것은 아니다.

나머지가 1보다 큰 상황에선 나머지의 수와 동일한 갯수만큼 각 숫자에 1씩 더해주면, 가장 편차가 적은 집합을 구성할 수 있게 된다.

 

풀이 코드

if(s < n)
{
    return {-1};
}

 

먼저, 예외처리이다. 만약, s가 n보다 작다면?
s 를 n으로 나눈 몫이 0이 된다. 최고의 집합은 모든 원소가 자연수가 되어야 하는데, s < n 인 상황에선 원소에 0이 포함되므로 s < n 인 경우에는 최고의 집합이 존재하지 않는다.

 

vector<int> Answer(n, 0);
    
int Share = s / n;
int Remain = s % n;

for(int i =  Answer.size() - 1; i  >= 0; i--)
{
    Answer[i] = Share;

    if(Remain > 0)
    {
        Answer[i] += 1;
        Remain--;
    }
}

이후, 위에서 말했던 것처럼 배열에 몫을 저장해주었고, 배열의 가장 뒤에서부터 나머지의 개수만큼 원소에 1을 더해주었다.

 

return Answer;

반복문이 끝난 후 배열을 반환해주면 된다.

 

 

코드 전문

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) 
{
    if(s < n)
    {
        return {-1};
    }
   
    vector<int> Answer(n, 0);
    
    int Share = s / n;
    int Remain = s % n;
    
    for(int i =  Answer.size() - 1; i  >= 0; i--)
    {
        Answer[i] = Share;
        
        if(Remain > 0)
        {
            Answer[i] += 1;
            Remain--;
        }
    }
        
    return Answer;
}