최고의 집합

https://programmers.co.kr/learn/courses/30/lessons/12938

전에 비슷한유형 한번 풀었는데 또 못풀었다.
dfs로 접근하려고 했는데, 이 문제 dfs로 접근하면 시간초과 난다.

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

using namespace std;

vector<int> solution(int n, int s) {
    vector<int> answer;
    
    if(s<n) 
    {
        answer.push_back(-1);
        return answer;
    }
    
    int idivision = s/n;
    int irest = s%n;
    int one = 1;
    
    if(irest == 0)
    {
        for(int i=0; i<n; i++)  answer.emplace_back(idivision);
    }
    else
    {
        for(int i=0; i<irest; i++)  
        {
            answer.emplace_back(idivision+one);
        }
        for(int i=0; i<n-irest; i++)
        {
            answer.emplace_back(idivision);
        }
    }
    sort(answer.begin(), answer.end(), [](int a, int b){
        return a<b;
    });
       
    
    return answer;
}

곱의 값이 최대가 나올 수 있는 경우는 숫자들이 s/n의 값이 몰려있을 경우이다.
s/n 의 값을 먼저 구하고 나머지가 0이 아닌 것의 개수만큼 +1을 해주거나 +1을 안해주거나 하면 된다.
dfs로 하면 낚이는 문제임.