최고의 집합 [Lv. 3] (C++)

프로그래머스

N개의 수의 합이 S인 집합들 중 모든 수의 곱이 가장 큰 집합을 찾아서 오름차순으로 출력하는 문제입니다.

 

풀이 방법

집합의 수들의 편차가 가장 적은게 답입니다.

N이 3이고 S가 9일 때는 ( 3, 3, 3 )

N이 5이고 S가 10일 때는 ( 2, 2, 2, 2, 2 )

N이 3이고 S가 11일 때는 (3, 4, 4)

 

즉 모든 경우의 수에 대해서 탐색할 필요 없이 (S / N) 을 answer 배열에 N번 넣어주고

(S % N)수 만큼 배열의 뒤에서부터 ++해주면 됩니다.

 

정답 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) {
    if (s < n)
        return {-1};
    
    vector<int> answer;
    
    int cnt = n;
    while(cnt--)
        answer.push_back(s / n);
    
    cnt = s % n;
    int idx = n-1;
    while(cnt--)
        answer[idx--]++;
    
    return answer;
}