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

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

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

 

 

#include <string>
#include <vector>

using namespace std;

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

    // n개의 자연수로 s를 만들 수 없는 경우
    if (n > s)
    {
        return { -1 };
    }
    
    // 초기에 n개의 자연수는 각각 (s / n)의 값을 가짐
    int qe = s / n;
    vector<int> answer(n, qe);

    // s에서 (int)(s / n) * n만큼을 제하기
    s -= n * qe;
    
    // 뒤에서부터 남은 숫자들을 1씩 더해줌
    for (int i = n - 1; i >= 0; --i)
    {
        ++answer[i];
        --s;
        if (s == 0)
        {
            break;
        }
    }

    return answer;
}

 

 

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

자연수의 개수 n은 1 이상 10,000 이하의 자연수입니다.
모든 원소들의 합 s는 1 이상, 100,000,000 이하의 자연수입니다.

 

합이 S가 되는 n개의 수를 고를 때, 각 원소의 곱이 최대가 되어야 한다.

주어진 수의 크기를 봤을 때 브루트포스나 이분탐색 등의 방법으로는

시간복잡도가 터질것이라는 점을 알 수 있다.

 

그렇다면 그리디적으로 풀어야 한다!

값을 가능한 동일하게 만들어 줄때 최대의 곱을 얻을 수 있다는 점을 눈치채면 문제풀이가 빨라진다.

 

일단 가능한 동일하게 만들어 주려면 초기에 N개의 각 원소는 S / N의 크기를 가진다.

그리고나서 S에서 (int)(S / N) * N만큼 빼준다.

문제에서 오름차순 배열을 요구했으므로, 남은 S만큼을 뒤에서부터 1씩 분배해주면 된다.