문제

Programmers Lv3, 최고의 집합

핵심

• 입력의 크기가 10,000이라 대략 $O(N^2)$이하 알고리즘을 사용한다.
• 자연수 n개로 이루어진 중복 집합 중 각 원소의 합이 S가 되는 집합에서 각 원소의 곱이 최대가 되는 집합을 구해야 한다.
• 자연수 중복 집합임을 명심해야 한다. 처음에 집합의 원소가 주어진다고 생각하여 DP 풀이로 잘못 접근했었다.

자연수 2개로 이루어진 집합 중 합이 9가 되는 집합 -> {1, 8}, {2, 7}, {3, 6}, {4, 5} 
자연수 3개로 이루어진 집합 중 합이 9가 되는 집합 -> {1, 1, 1}, {1, 1, 7}, {1, 2, 6}, {1, 3, 5} ...
자연수 4개로 이루어진 집합 중 합이 9가 되는 집합 -> {1, 1, 1, 6} ...

개선

• 해당 문제를 완전 탐색으로 풀 수 있을까? 자연수 n개로 이루어진 집합 중 합이 S가 되는 집합을 중복 조합으로 모두 구한다면 1~9를 매번 선택할 수 있으므로 $O(9^N)$ 시간복잡도를 가진다.
• N이 10,000까지 가능하기 때문에 아래처럼 DFS로 모든 조합을 완전탐색하면 시간 초과가 뜬다.

void dfs(int depth, int sum, int n, int s) {
    
    if (depth == n) {
		if (sum == s) {
			int cur_multiple_sum = 1;
			for (int i = 0; i < n; ++i) {
				cur_multiple_sum *= is_selected[i];
			}		
			if (cur_multiple_sum > multiple_sum) {
				multiple_sum = cur_multiple_sum;
				answer = vector<int>(is_selected, is_selected + n);
			}
		}
		return;
    }

	for (int i = 1; i <= 9; ++i) {
		is_selected[depth] = i;
		dfs(depth + 1, sum + i, n, s);
	}
}

• 값이 균등할수록 곱셈의 결과가 커진다는 사실을 알면 쉽게 풀 수 있다.
  • 쉬운 예로 사각형에서 하나의 가로와 세로 길이가 합쳐서 8일 때 넓이를 가장 크게 구하려면? 가로세로 길이가 균등할 때 넓이는 가장 커진다.
  • 4 * 4 = 16
  • 5 * 3 = 15
  • 6 * 2 = 12
  • 7 * 1 = 7
• 먼저 수를 균등하게 나누어 주고, 나머지가 생기면 뒤의 원소부터 하나씩 보충해 주면, 오름차순으로 집합을 만들 수 있다.

코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(int n, int s) {
    
    int share = s / n;
    int remainder = s % n;
    
    if (share < 1) return {-1};
    
    vector<int> answer(n, share);
    for (int i = 0; i < remainder; ++i) {
        answer[n - i - 1] += 1;
    }
    return answer;
}

import java.util.*;

class Solution {
    public int[] solution(int n, int s) {
        
        int share = s / n;
        int remainder = s % n;
        
        if (share < 1) {
            return new int[]{-1};
        }
        
        int[] answer = new int[n];
        Arrays.fill(answer, share);
        for (int i = 0; i < remainder; ++i) {
            answer[n - i - 1] += 1;
        }
        return answer;
    }
}