[프로그래머스] level 3 - 최고의 집합

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

코딩테스트 연습 - 최고의 집합 | 프로그래머스

 본 문제는 자연수 n 개로 이루어진 중복 집합 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 한다. 문제의 조건은 다음과 같다.

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

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

왠지 예제를 보면 { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 } 다 만들어보고, 계산을 해야 될 거 같은데 실제로 그렇게 코딩하면 예제 TC는 맞지만 나머지 TC와 효율성에서 다 틀리게 된다. (직접 해봤다..) 따라서 다른 방법을 사용해야 한다.

문제의 힌트는 예제 TC에 있다.

1. 2개의 숫자로 이루어진 집합 중 합이 8인 최고의 집합은 { 4, 4 }
2. 2개의 숫자로 이루어진 집합 중 합이 9인 최고의 집합은 { 4, 5 }

여기에 힌트를 얻어 다음과 같은 예제를 만들어 봤다.

1. 4개의 숫자로 이루어진 집합 중 합이 12인 최고의 집합은 { 3, 3, 3, 3 }
2. 4개의 숫자로 이루어진 집합 중 합이 13인 최고의 집합은 { 3, 3, 3, 4 }
3. 4개의 숫자로 이루어진 집합 중 합이 14인 최고의 집합은 { 3, 3, 4, 4 }

즉, s를 n으로 나눈 몫을 집합에 넣어야 하며, 나머지의 개수 만큼 집합에서 1씩 증가시켜야 한다. 쉽게 말하자면 12 / 4 = 3 이고, 12 % 4 = 1 이므로 3이 3번 4가 1번인 집합을 만들어야 한다.

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<int> solution(int n, int s) {
    vector<int> answer;
    int x = s/n;
    int y = s%n;
    if (x == 0) {
        answer.push_back(-1);
        return answer;
    }
    for (int i = 0; i < n-y; i++) {
        answer.push_back(x);
    }
    for (int i = 0; i < y; i++) {
        answer.push_back(x+1);
    }
    return answer;
}