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

https://school.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 }가 최고의 집합입니다.

 

[문제 조건]

 

최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 return 해주세요.

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

 

[문제 풀이]

생각보다 문제가 간단하다.

 

S를 n개의 수로 나눴을때 n개의 수의 곱이 최대가 되려면 균일하게 나누는 수 밖에 없다.

 

예를 들어 s = 15, n = 3이라 했을 때 { 5, 5, 5} , { 4, 5, 6 } , { 3, 5, 7 }.... 과 같이 나누었을 때 각각 125, 120, 105의 값을 가지게 된다. 이것을 다르게 표현하면 s/n = k라고 했을때 { k, k, k } , {k-1 , k , k+1} , {k-2, k ,k+2} 가 되고 각각 k^3 , k^3 - k , k^3 - 4k의 값을 가지된다. 따라서 k k k로 분배해주는 것이 곱이 항상 최대가 되는 경우다.

 

이때 s를 n으로 나누었을 때 나오는 나머지는 균일하게 분배해주어야 한다.

 

s=17, n =3 일때 {5,5,7} , {5,6,6} 의 경우를 보면 175, 180이 나온다. 이것을 다시 자세히보면 5의 경우 중복되니 없다고 생각하면 결국에는 {k , k+2 } , {k+1, k+1}의 값을 비교하면 k^2 + 2k, k^2 + 2k + 1의 값을 가진다. 따라서 후자의 경우가 값이 더 크다. 

 

[소스 코드]

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(int n, int s) {
    vector<int> answer;
    
    if(s/n==0) { answer.push_back(-1); return answer; }
    
    int div = s/n;
    int rest = s%n;
    
    for(int i=0; i<n; i++) 
    {
        answer.push_back(div);
        if(i<rest) answer[i]++;
    }
    sort(answer.begin(), answer.end());
  
    
    return answer;
}

이렇게 접근하는게 맞는지는 잘 모르겠지만 됐으니 장땡

굳