[C++로 풀이] 최고의 집합⭐⭐⭐

📌 최고의 집합

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이

✈ 1 차 풀이 : DFS로 중복 조합을 구하려 했던 시도 (⏰시간초과)

vector<int> DFS(int& n, int& s, int& max, long long mul, vector<bool>& visited, vector<int>& arr, vector<int> comb, int sum, int index, int depth)
{
    vector<int> answer;

    if (depth == n - 1) {
        comb[depth] = s - sum;
        mul *= (long long)s - sum;
        visited[s - sum] = true;
        if (max < mul) {
            max = mul;
            answer = comb;
        } 
        return answer;
    }

    for (int i = index; i < arr.size(); i++) {
        if (visited[arr[i]] == false) {
            comb[depth] = arr[i];
            sum += arr[i];
            mul *= arr[i];
            answer = DFS(n, s, max, mul, visited, arr, comb, sum, i, depth + 1);
            sum -= arr[i];
            mul /= arr[i];
        }
    }

    return answer;
}

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

    if (n > s) { // n이 s보다 클 때는 n개로 합이 s가 되게 만들 수 없다. 3개의 집합으로 2를 표현한다면 못해도 {1 1 1}로 해야하는데 이는 2를 넘긴다. 
        answer.push_back(-1);
        return answer;
    }

    if (n == 1) {
        answer.push_back(s);
        return answer;
    }

    vector<int> arr;
    for (int i = 1; i <= s - n + 1; ++i)
        arr.push_back(i);

    vector<int> comb(n);
    vector<bool> visited(arr.size());
    int max = 0;
    answer = DFS(n, s, max, 1, visited, arr, comb, 0, 0, 0);

    return answer;
}

아이고 복잡하다.. 이 풀이는 문제의 예제 3개는 통과되지만 제출하면 이렇게 거의 모든 케이스에서 시간 초과가 발생한다. 그리하여 이 풀이를 집어 치우고 좀 더 고민하다가 아래 2 차 풀이로 간단하게 풀 수 있게 되었다. 괜히 고생했네 ㅠ ㅜ.. 제한 사항만 봐도 입력 크기가 장난 아닐 것이라는 것을 예상할 수 있으니 이런 경우엔 O(n^2)을 넘을 수 있는 재귀 호출은 삼가하자.

대충 아래와 같은 로직을 생각하며 풀이한 코드였다.

• 깊이가 n - 1이 되기 전까지 중복 조합을 구하는 DFS를 진행한다.
  • comb에 중복 조합을 저장하고
  • sum 과 mul에 각각 현재까지 모인 조합의 합과 곱을 저장한다.
• 깊이가 n - 1이 되면
  • ✨n번째 자리는 s - sum 값으로 결정한다. 예를 들어 s = 9, n = 4 라면 현재 [1, 2, 2] 까지 완성된 조합이라면 마지막 자리는 4 가 되야 한다. [1, 2, 2, 4]
  • 마지막 원소로 결정된 이 s-sum은 방문 체크를 한다. 위 예로 들자면 5 로 시작하는 조합은 만들지 않도록.. [4, 5]로 완성된 조합이라면 [5, 4]가 나와선 안된다.
  • 이렇게 DFS 종료시 여태까지의 mul 곱과 현재까지의 max를 비교해 max를 업뎃한다.

처참한 시간 초과..⭐

✈ 2 차 풀이 ⭕

#include <string>
#include <vector>

using namespace std;

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

    if (n > s) { // 만들 수 없는 경우
        answer.push_back(-1);
        return answer;
    }

    for(int i = 1; i <= n; i++)
        answer.push_back(s / n);
    
    for(int i = 1; i <= s % n; i++)
        answer[n - i]++;

    return answer;
}

좀 더 고민을 해보니 이 문제는 야근 지수 문제처럼 조합 내 원소들이 균등할 때 그 곱이 가장 크다는 것을 생각하며 문제를 풀면 이렇게 DFS 같은거 쓸 필요 없이 간단하게 O(n)으로 풀이할 수 있었다.

[3, 5] 보단 [4, 4] 의 곱이 더 크다. 원소들이 고만고만할 수록 그 곱이 더 커진다. 따라서 균등하게 만들면 된다!

• 균등하게 만드는 방법 (ex. n = 4, s = 10)
  • 1️⃣ s / n 몫 값으로 조합의 n개를 채운다.
    • 👉 10 / 4 = 2 👉 [2, 2, 2, 2]
  • 2️⃣ 조합에 반영되지 못한 s % n 나머지 값에 해당하는 개수만큼 1씩 더해준다.
    • 👉 10 % 4 = 2 👉 [2, 2, 3, 3] (끝에 2개를 1씩 더해준다.)

이렇게 합이 s가 되게끔 할 수 있고 더불어 균등하게 만들어 곱이 최대로 커지게 만들 수 있었다. 따라서 n = 4, s = 10 경우엔 [2, 2, 3, 3]이 최고의 집합이 된다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기