프로그래머스 최고의 집합 C++

 

자연수 n개로 이루어진 중복 집합 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 한다.

 

1. 각 원소의 합이 s가 되는 수의 집합

2. 위 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합

 

집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질때

조건을 만족하는 최고의 집합을 리턴하는 문제이다

 

리턴할 경우 answer는 오른차순 정렬된 1차원 배열로 리턴해야하며,

만약 최고의 집합이 없는 경우 -1을 채워서 리턴해라

 

문제에서 나오는 최고의 집합을 만드는 방법은 생각보다 간단하다

 

각 원소들이 서로 최대한 균등한 값을 가지도록 만들면 된다.

 

주어진 s 원소의 합에서 n을 나눈 값을 반올림을 이용해 

multiset에 하나씩 저장한다.

그 다음 빠진 수와 개수만큼 s와 n에서 빼주고 n번만큼 반복하여 multiset에 삽입해주면

최고의 집합을 형성하게 된다.

 

그다음 만들어진 multiset은 자동 정렬이 되어있기에

반복문을 통해 answer에 push_back을 해주면 된다.