[프로그래머스 lv3] 최고의 집합 풀이

해설

가장 단순하게 백트래킹 방법이 떠오르지만, 백트래킹으로 n개의 합이 S가 되는 모든 경우를 탐색하면 TLE가 발생한다.

dp 점화식도 세울 수 있지만, n과 s의 입력범위가 너무 커 해당 방법도 TLE가 날 것이 분명하다.

 

이 문제는 완전 탐색 없이 간단한 트릭을 통해 해결할 수 있다.

특정 배열의 원소의 곱이 최대가 되려면, 각 원소가 최대한 균등해야 한다.

예를 들어 n = 4 이고 s = 10일 때, 각 원소를 최대한 균등하게 하려면 s/n = 10/4 = 2 를 4개 마련하고 {2, 2, 2, 2} 여기에 나머지 2를 하나씩 더해준다. 결과적으로 {2, 2, 3, 3}이 최대 곱을 만드는 배열이 된다.

 

n > s 이면 자연수 n개의합이 s가 되는 경우가 없으므로 {-1}을 리턴한다.

n <= s 인 경우, s/n을 n개 균등하게 구성하고 s%n을 마지막 원소로 부터 하나씩 나누어준다.

최종 배열을 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

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