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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

이 문제는 그리디하게 해결했다. 이 문제의 핵심 아이디어는 곱하는 수들 간의 차이가 가장 적게 하는 것이다.

만약 s가 9이고, n이 3이라고 가정해보자. 이 때는 3, 3, 3을 곱해야 가장 크다는 것을 직관적으로 알 수 있을 것이다. 이번엔 s가 24이고 n이 6을 생각해보자. 이 역시 4, 4, 4, 4, 4, 4를 곱해야 최대값이 된다는 것을 알 수 있다. 지금까지의 예시는 모두 s를 n으로 나눈 나머지가 0인 경우였다.

이번엔 s가 n으로 나누어떨어지지 않는 경우를 생각해보자. s가 11이고 n이 3인 경우이다. 이 경우 역시 위의 핵심 아이디어에서 말한거처럼 가장 근접한 수들 3개의 곱으로 만들고 싶다. 이는 3, 4, 4가 된다는 것을 알 수 있다. 이것을 어떻게 구현해야할까? 11을 3으로 나누면 나머지가 2가 된다. 이 말은 9는 3으로 나누어 떨어진다는 말이 된다. 그렇기 때문에 3, 3, 3을 배열에 저장한 뒤, 나머지 2를 하나씩 더해주는 방식을 사용하면 된다. 이러한 방법으로 3, 4, 4를 구할 수 있다.

아래의 코드에서는 나머지가 0인 경우와 0이 아닌 경우의 분기를 나누지 않고 구현했다는 것을 참고하기 바란다.

코드

C++

	#include <string>
	#include <vector>
	#include <algorithm>
	using namespace std;
	vector<int> solution(int n, int s) {
	vector<int> answer;
	// 집합을 만들 수 없는 경우
	if(s < n) return {-1};
	int rest = s % n;
	// n개의 수를 벡터에 저장
	for(int i=0; i<n; i++) answer.push_back((s - rest) / n);
	// 나머지만큼 1 증가시켜준다
	for(int i=0; i<rest ;i++) answer[i]++;
	// 오름차순으로 정렬
	sort(answer.begin(), answer.end());
	return answer;
	}

view raw 최고의 집합.cpp hosted with ❤ by GitHub