[프로그래머스/C++] 최고의 집합

✅ LV.3

✏️ 1차 솔루션

⭐️ backtracking 조합

1. 합과 곱을 저장해가며 backtracking 하며 n 개의 조합 만들기
2. n 개의 조합이 완성될 때마다 현재 곱과 이전에 저장된 곱을 비교해서 현재 곱이 더 크면 answer 벡터 교체

🚨 1차 trouble

예상대로 시간초과..^^

✏️ 최종 솔루션

⭐️ Greedy

1. s 가 n보다 작으면 숫자를 만들 수 없기 때문에 -1
2. s 를 n 으로 나눴을 때 나누어 떨어지면 n 개의 원소가 s/n 일 때 곱이 가장 커짐
3. 나누어 떨어지지 않는다면 나머지만큼의 원소에 1을 추가
   ➡️ 원소의 값이 비슷할수록 곱이 커지기 때문

✏️ 최종 code

#include <string>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) {
    vector<int> answer;
    
    if(s<n) {
        answer.push_back(-1);
        return answer;
    }
    
    for(int i=0;i<n;i++) {
        answer.push_back(s/n);
    }
    
    // 나누어 떨어짐
    if(s%n!=0) for(int i=0;i<s%n;i++) answer[i]++;
    
    reverse(answer.begin(),answer.end());
    
    // 나누어 떨어지지 않음
    return answer;
}