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

프로그래머스의 최고의 집합(Lv3) 문제이다.

[ 문제풀이 ]

문제를 단계별로 나누어서 한번 접근해보자.

#1. 곱이 최대가 되는 경우

우리는 각 원소의 합이 S를 이루면서, 동시에 그 원소들의 곱이 최대가 되는 경우를 구해야 한다.

그럼 과연 어느 경우에 그 곱이 최대가 될까 ??

문제에서 나와있는 설명을 가지고 한번 이야기해보자.

자연수 2개로 이루어진 집합 중 합이 9가 되는 집합을 만들어보자.

[ 1 , 8 ]

[ 2 , 7 ]

[ 3 , 6 ]

[ 4 , 5 ]

이렇게 4개가 존재한다. 그 중에 곱이 가장 큰 경우는 마지막 [ 4 , 5 ] 경우이다.

한가지 예시만 더 들어보자.

자연수 3개로 이루어진 집합 중 합이 7이 되는 집합을 만들어 보자.

[ 1 , 1 , 5 ]

[ 1 , 2 , 4 ]

[ 1 , 3 , 3 ]

[ 2 , 2 , 3 ]

위와 같이 총 4개가 존재한다. 그 중에 곱이 가장 큰 경우는 마지막 [ 2 , 2 , 3 ] 이 된다.

그럼 첫 번째 예시의 결과로 나온 [ 4 , 5 ] 와 두 번째 예시의 결과로 나온 [ 2 , 2 , 3 ] 을 한번 보자.

어떤 공통점이 있을까 ??

뭐 이 2개의 직관적인 공통점을 말하는 것은 아니다. 이 2개의 공통점은, "만들어진 다른 집합들과 비교했을 때, 가장 숫자들 간의 차이가 작다" 라는 것이다.

< 첫 번째 Case >

[ 1 , 8 ] : 원소간의 차이 중 최대차이가 7

[ 2 , 7 ] : 원소간의 차이 중 최대차이가 5

[ 3 , 6 ] : 원소간의 차이 중 최대차이가 3

[ 4 , 5 ] : 원소간의 차이 중 최대차이가 1

< 두 번째 Case >

[ 1 , 1 , 5 ] : 원소간의 차이 중 최대차이가 4

[ 1 , 2 , 4 ] : 원소간의 차이 중 최대차이가 2

[ 1 , 3 , 3 ] : 원소간의 차이 중 최대차이가 2

[ 2 , 2 , 3 ] : 원소간의 차이 중 최대차이가 1

이렇게 주황색으로 칠해진 경우들을 보게 되면, 원소간의 차이가 굉장히 작다는 공통점을 가지고 있다.

그리고 이 경우가 곱이 최대가 되는 경우라는 것을 알 수 있다.

즉 ! "원소간의 차이를 최소화로 만드는 집합이, 원소의 곱이 최대가 되는 집합이 된다."

#2. 집합 만들기

그럼 #1에서 이야기했던, 원소간의 차이가 최소로 이루어진 집합을 어떻게 만들 수 있을까 ??

바로 "나누기와 모듈러 연산을 통해서" 만들 수 있다.

자연수 3개로 이루어진 집합 중 합이 7이 되는 경우를 생각해보자.

먼저, 가장 차이를 작게 만들기 위해서 7을 3개로 한번 나눠보자. 7 / 3 = 2 라는 값을 가지게 된다.

그럼, 일시적으로 먼저 [ 2 , 2 , 2 ] 라는 집합을 만드는 것이다.

하지만, [ 2 , 2 , 2 ] 는 3개의 합으로 7을 만들 수가 없다.

그럼 7을 만들기 위해서는 얼마만큼 더해주어야 할까 ?? '1'만큼을 더 더해주면 된다.

이 '1'은 어디서 나온 걸까 ?? 바로 7 % 3 에서 나온 값이다.

즉, "자연수 3개로 이루어진 집합 중, 합이 7이 되는 집합을 만들기 위해서는 7을 3으로 나눈 수 만큼을 일시적으로 넣어주고,

7 % 3 한 값 만큼 원소들에 더해주면 된다" 는 것이다.

그래서 '1'을 더해줘야 하므로, 하나의 원소에 '1'을 더해주면 [ 2 , 2 , 3 ] 이 된다.

그럼 자연수 3개로 이루어진 집합 중 8이 되는 경우를 생각해보자.

똑같이 8 / 3 = 2 로, [ 2 , 2 , 2 ] 라는 집합을 만들 것이다.

그런데, 추가적으로 더해줘야 하는 값이 8 % 3 = 2 만큼이 더 존재한다.

그럼, [ 2 , 2 , 4 ] 로 만들어주는게 좋을까 ? [ 2 , 3, 3 ] 으로 만들어 주는게 좋을까 ?

아까도 말했듯이, 원소간의 차이를 최소화 시키는 것이 더 큰 결과를 얻을 수 있다.

즉 ! [ 2 , 3 , 3 ] 으로 만들어 주면 된다.

#3. 만들 수 없는 경우

문제에서 만들 수 없는 경우에는 -1을 return 하라고 했는데, 이 경우는 어느 경우일까 ??

바로, n > s 인 경우이다.

자연수 3개로 이루어진 집합 중 합이 2가 되는 집합을 만드세요.

만들 수 있을까 ?? 자연수 3개를 더해서 그 합이 2가 되도록 만들어야 하는 상황이다.

불가능하다.

n > s 인 경우에는 바로 -1 을 return 해버리면 된다.

[ 소스코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
vector<int> solution(int n, int s)
{
    vector<int> answer;
    if (n > s)
    {
        answer.push_back(-1);
        return answer;
    }
    
    int Basic = s / n;
    int Extra = s % n;
    answer.assign(n, Basic);
    // assign(a , b) = vector에 b값을 가지는 원소를 a개 push한다.
    for (int i = answer.size() - 1; i >= 0 && Extra > 0; i--)
    {
        answer[i]++;
        Extra--;
    }
    
    return answer;
}