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

링크

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

프로그래머스

풀이

집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 구해야 되는 문제 이다.

 

예를 들어 원소의 개수가 2개 이고 원소들의 합이 6이라고 할 때 원소를 나누어 보았을 때

1,5  2,4  3,3  이렇게 3개로 나눌 수 있고 각각 원소의 곱은 5, 8 ,9이다.

 

이때 원소의 합을 원소의 개수로 나누었을 때 나오는 값에 가까운 수가 많을수록 원소들의 곱이 가장 크다는 것을 알 수 있다. 

 

하지만 원소들의 합이 원소의 개수로 나누어 떨어지지 않을 때는 예를 들어 원소의 개수가 3개 이고 합이 11과 같은 경우에는 3,3,3으로 나누고 나머지가 2 이기 때문에 3, 4 ,4로 만들어 주면 최대의 곱을 만들 수 있습니다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 1010
const int INF = 2000000000;

using namespace std;

typedef long long int ll;
vector<int> solution(int n, int s) {
	int mok = s / n;
	int na = s %n;
	vector<int> answer;

	if (mok == 0) {
		answer.push_back(-1);
		return answer;
	}
    
	for (int i = n-1; i >=0; i--) {
    	//나머지가 있으면 원소에 1을 더해줌
		if (i < na)
			answer.push_back(mok + 1);
		else
			answer.push_back(mok);

	}
	return answer;
}