[프로그래머스/C++] 최고의 집합

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

코딩테스트 연습 - 최고의 집합

최고의 집합

문제

자연수 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 이하의 자연수입니다.

 

풀이

입출력 예시

 

풀이

수를 분할해서 서로의 곱이 가장 크도록 하는 방법은, 수들의 차이를 가장 작도록 만드는 것이다.

 

위의 예시예서 9를 2개의 수로 분할한다고 하면, { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 } 가 된다.

이 중에서 수들의 차이가 가장 작은 것은 { 4, 5 } 이며, 서로의 곱이 가장 큰 것도 { 4, 5 } 이다.

 

이 집합을 구하는 방법은,

1. 수(s)를 분할하려는 개수(= 집합의 원소의 수) n으로 나누어준다.

2. 나눗셈의 결과에서 몫이 집합의 원소가 된다.

2-1. 만약 나머지가 0이 아니라면 나머지만큼의 수를 각각 분배해준다.

 

n = 3이고 s = 11일 경우에는 몫이 3, 나머지가 2가 된다.

그러면 { 3, 3, 3 } 이라는 집합이 나오게 되는데, 나머지 2를 집합의 원소에 각각 분배해서

{ 3, 4, 4 } 라는 집합을 얻을 수 있다. 이 경우가 각 원소의 곱이 최대가 되는 집합이 된다.

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) {
    vector<int> answer;
    
    if (n > s) {
        return { -1 };
    }
    
    int a = s / n;
    int b = s % n;
    
    for (int i = 0; i < n; i++) {
        if (i >= n - b) {
            answer.push_back(a + 1);
        }
        else {
            answer.push_back(a);
        }
    }
    
    return answer;
}