0. 문제
https://school.programmers.co.kr/learn/courses/30/lessons/12938
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
1. 접근
최대 만 개의 숫자 조합을 구하는건 말이 안된다고 생각했다.
집합의 곱이 최대가 되는 경우를 생각해보니 원소들이 평균값에 근접할수록 곱이 최대가 된다는 사실을 확인,
해당 전략으로 접근하였다.
2. source code
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> solution(int n, int s) {
vector<int> answer;
int mid = s/n;
//불가능할 때
if(mid == 0){
answer.push_back(-1);
return answer;
}
int div = n;
for(int i=0; i<n -1; i++){
int cur = s/div;
answer.push_back(cur);
s-=cur;
div--;
}
answer.push_back(s);
sort(answer.begin(), answer.end());
return answer;
}
3. 추가
[c++/프로그래머스] 최고의 집합
규칙 찾아 구현하는 문제
velog.io
최적화 하면 위 블로그와 같은 코드를 작성할 수 있다.
원리는 동일하나 몫을 (평균값 + 1)로 배분하는 방식으로 접근하였다.
조금 더 효율적이고 깔끔하게 코드를 작성하는 방법인 듯 하다.