Programmers - 최고의 집합

---

title: Programmers - 최고의 집합
date: 2022-10-12
tags:

• Algorithm

---

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

문제 요약

자연수 n개로 구성 가능한 모든 집합 중 합이 s가 되며, 그 중 각 원소의 곱이 가장 큰 집합을 구한다.
해당 집합을 오름차순으로 정렬하거나, 만들 수 없다면 -1을 넣어 return한다.

문제 풀이

Level 설정이 잘못된 문제인 것 같다.
우선 n개의 자연수이기에 n <= s 라면 집합은 구성이 가능하다. 고로 s < n 이라면 -1을 넣어 바로 return한다.
합이 s일 때는 곱을 가장 크게 만들어야 하며, 이는 집합이 가장 Balanced할 경우(편차, 분산 등이 제일 작을 경우) 곱이 제일 커진다.


우선 s < n 인지 확인하여 구성이 불가능한 경우를 먼저 처리한다.
s / n의 int값은 집합을 구성하는 자연수 중 가장 작은 값이 된다. n - ( s % n ) 개가 존재하므로 우선 넣어준다.
이후, 이전에 넣은 값 + 1 을 남은 개수만큼 넣어준다. 0 == ( s % n ) 일 경우 이전 처리에서 모든 자연수를 넣게 된다.

프로그램

#include <vector>

using std :: vector ;

vector < int > solution ( int n , int s )
{
    vector < int > answer ;



    if ( s < n )            // Can't make set
        return { -1 } ;


    int iLow = s / n ;
    int iLowCount = n - ( s % n ) ;

    for ( int i = 0 ; i < iLowCount ; ++i )
        answer.emplace_back ( iLow ) ;
    for ( int i = iLowCount ; i < n ; ++i )
        answer.emplace_back ( iLow + 1 ) ;


    return answer ;
}