프로그래머스] C++ 연습문제 - 최고의 집합(level 3)

해당 문제는 프로그래머스 코딩테스트 연습에 있는 문제입니다.

아래 링크를 통해 풀 수 있습니다.

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

1. 문제

자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 집합으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.

1. 각 원소의 합이 S가 되는 수의 집합
2. 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합

예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다.
{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }
그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다.

집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요.

제한사항

• 최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 return 해주세요.
• 만약 최고의 집합이 존재하지 않는 경우에 크기가 1인 1차원 배열(list, vector) 에 -1 을 채워서 return 해주세요.
• 자연수의 개수 n은 1 이상 10,000 이하의 자연수입니다.
• 모든 원소들의 합 s는 1 이상, 100,000,000 이하의 자연수입니다.

---

입출력 예

n	s	result
2	9	[4, 5]
2	1	[-1]
2	8	[4, 4]

입출력 예 설명

입출력 예#1
문제의 예시와 같습니다.

입출력 예#2
자연수 2개를 가지고는 합이 1인 집합을 만들 수 없습니다. 따라서 -1이 들어있는 배열을 반환합니다.

입출력 예#3
자연수 2개로 이루어진 집합 중 원소의 합이 8인 집합은 다음과 같습니다.

{ 1, 7 }, { 2, 6 }, { 3, 5 }, { 4, 4 }

그중 각 원소의 곱이 최대인 { 4, 4 }가 최고의 집합입니다.

2. 조건

1. 구해야할 목표 값인 자연수 s가 주어진다.

2. 자연수 n이 주어지는데 n은 s를 만들기 위한 자연수의 갯수이다.

3. s의 자연수를 만들기 위해서 n개의 자연수가 필요한데, n개의 자연수의 합이 s가 되면 된다.

4. n개의 자연수는 숫자가 중복될 수 있다.

5. 수많은 n개의 자연수 중 자연수 n개를 모두 곱하였을 때 가장 큰 값을 지닌 자연수들을 구하여라.

6. 자연수를 구할 수 없다면 -1을 리턴해라.

3. 풀이

이 문제의 풀이는 간단합니다.

바로 곱샘과 중복숫자를 이용하는 것입니다.

최대 곱하기를 구하는 숫자는 해당 자연수 S를 N으로 나눴을 때, 

중간 값들을 곱하면 가장 큰 수가 됩니다..

예를들어 10을 이루는 자연수 2개의 집합은 다음과 같습니다.

{1, 9}, {2, 8}, {3 , 7}, {4, 6}, {5, 5}.

여기서 가장 큰 곱셈의 집합은 {5, 5} 입니다.

즉, 10을 2로 나눴을 때 나머지가 0이라면 중간 값이 가장 큰 숫자란 뜻입니다.

나머지가 있다면?? 중간 값을 기준으로 나머지를 분배해주면 됩니다.

그럼 97을 10개의 자연수로 나눈다면??

9 = 3개

10 = 7개 인 것이 곱했을 때 가장 큰 수가 됩니다.

97을 10으로 나누고, 나머지를 1씩 분배해준 것입니다.

계산해보면 다음과 같이 됩니다.

9 = 10개, 나머지 = 7개.

그럼 7을 1씩 분배해주면 위와같은 값이 나오게 됩니다.

4. 코드

#include <string>

#include <vector>

using namespace std;

vector<int> solution(int n, int s) {

    vector<int> answer;

    if(n > s){

        answer.emplace_back(-1);

        return answer;

    }

    int quo = s / n;

    int rem = s % n;

    int num = 0;

    

    if(s % n != 0) num = 1; //나누어 떨어지지 않는다면 나머지를 1씩 분배

    

    for(int i = 0; i < n; i++)

        if(i >= n - rem) answer.emplace_back(quo + 1);

        else answer.emplace_back(quo);

    

    return answer;

}