[Programmers] 최고의 집합

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12938

코딩테스트 연습 - 최고의 집합

집합의 원소 간의 차가 최소일 때 각 원소 간의 곱이 최대가 되는 것은 자명합니다.

 

따라서, 알고리즘은 아래와 같습니다.

1. s를 n으로 나누었을 때 1보다 작을 경우 원소들의 합이 s가 될 수 없으므로 바로 -1을 반환해줍니다.

2. 우선, 벡터에 (s / n)을 n개 넣어줍니다.

2.1 여기서 (s / n)은 s를 n으로 나누어준 후 소수점 이하 값들을 버린 값입니다.

3. 2.1에서 언급했듯이 소수점 이하 값들을 버렸으므로 (s / n) * n을 할 경우 s보다 작을 수 있으며 해당 값을 k라고 하겠습니다.

3.1 (s - k)만큼 벡터 내 원소들을 선정해 1씩 증가시키면 집합의 원소 간의 차가 최소가 되므로 각 원소 간의 곱이 최대가 됩니다.

 

	#include <string>
	#include <vector>
	using namespace std;
	vector<int> solution(int n, int s) {
	if (s / n == 0) {
	return { -1 };
	}
	vector<int> answer;
	for (int i = 0; i < n; i++)
	{
	answer.push_back(s / n);
	}
	int total = (s / n) * n;
	for (int i = 0; i < s - total; i++)
	{
	answer[n - (i + 1)]++;
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~