[프로그래머스] Level 3. 최고의 집합

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

프로그래머스

 

 

해결 방법

처음엔 [1,1,1,1...,1] 부터시작하여, 하나씩 더하는 방식으로 모든 경우의 수를 구해서 풀었다. 그러나 시간초과가 발생했다. 탐색은 아니고, 균등하게 분배할 수록 곱이 커진다는 것을  이용하여 푸는 문제였다. N개짜리 배열을 만들고 거기에 최대한 균등하게 배분한 뒤, 남은 수는 각 원소에 1씩 더하는 방법으로 간단하게 해결할 수 있는 문제였다.

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) {
    
    if(n>s) return vector<int>(1,-1);
    
    
    int val = s/n;
    vector<int> answer (n, val);
    int remain = s - val*n;
    int idx =answer.size()-1;

    for(int i=0; i<remain; i++){
        answer[idx]+=1;
        idx--;
    }
    
    return answer;
}