Level 3. 최고의 집합

Level 3. 최고의 집합

 

 

재귀를 이용해 합이 s가 되는 모든 n개의 조합을 구해 계산하는 방법이다.

• 나를 제외한 나머지에 해당하는 조합을 구한 후 나를 앞에 붙이는 방식이므로, vector보다는 deque을 사용했다.

 

하지만, 시간 초과가 발생했다.

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

deque<deque<int>> get_sum_sets(int num, int n, int sum)
{
    if (n == 1 && num <= sum)
        return {{sum}};

    deque<deque<int>> result;

    for (int i = num; i <= sum - n + 1; ++i)
    {
        for (deque<int>& deq : get_sum_sets(i, n - 1, sum - i))
        {
            deq.emplace_front(i);

            result.emplace_back(deq);
        }
    }

    return result;
}

vector<int> solution(int n, int s)
{
    int max = -1;
    vector<int> answer {-1};

    for (deque<int>& deq : get_sum_sets(1, n, s))
    {
        int mul = 1;

        for (int e : deq)
            mul *= e;

        if (max <= mul)
            answer = vector<int>(deq.begin(), deq.end());
    }

    return answer;
}

 

재귀로 시간 초과가 발생했다면, 접근 방법 자체를 바꿔야 한다는 뜻이다.

 

생각해보니 평균을 이용하면 될 것 같았고 while문을 사용해 재귀적인(?) 방법으로 해결했다.

• 아래 방법은 정렬하지 않아도 오름차순으로 배치된다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> solution(int n, int s)
{
    if (n > s)
        return {-1};

    vector<int> answer;

    while (0 < n)
    {
        int num = s / n--;

        s -= num;

        answer.emplace_back(num);
    }

    return answer;
}

 

모든 원소는 평균 or 평균 + 1임을 증명해서 반복문을 전혀 사용하지 않고 바로 해결한 사람도 있었다..

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> solution(int n, int s)
{
    if (n > s)
        return {-1};

    int avg = s / n, mod = s % n;
    vector<int> left(n - mod, avg), right(mod, avg + 1);

    left.insert(left.end(), right.begin(), right.end());

    return left;
}