(프로그래머) (C++) (12938) 베스트 세트

by

(문제 소스)

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

1. 문제

설명

'추천 관련글,

n개의 자연수의 중복집합(다집합, 이하 편의상 총칭하여 “집합”이라 함) 중에서 다음 두 가지 조건을 만족하는 집합을 최적집합이라 한다.

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

예를 들어, 2개의 자연수 집합에는 합이 9인 4개의 집합이 있습니다.
{1, 8}, {2, 7}, {3, 6}, {4, 5}
그 중 각 원소의 곱이 가장 큰 {4,5}가 가장 좋은 집합이다.

세트의 요소 수인 n과 모든 요소의 합인 s를 매개변수로 주어 최적의 세트를 반환하는 solve 함수를 완성합니다.

제한

  • 최고의 문장 오름차순으로 정렬된 1차원 배열(리스트, 벡터) 로 돌아가주세요
  • 베스트 세트가 없을 때 크기가 1인 1차원 배열(목록, 벡터) 에게 -하나 작성하여 반송해 주십시오.
  • 자연수 n은 1에서 10,000 사이의 자연수이다.
  • 모든 요소의 합 s는 1보다 크거나 같고 100,000,000보다 작거나 같은 자연수입니다.

I/O 예시


I/O 예시 설명

I/O 예제 #1
문제의 예와 같습니다.

I/O 예제 #2
합이 1인 두 개의 자연수 집합을 만들 수 없습니다. 따라서 -1을 포함하는 배열을 반환합니다.

I/O 예제 #3
합이 8인 두 자연수의 집합은 다음과 같습니다.

{1, 7}, {2, 6}, {3, 5}, {4, 4}

그 중 각 원소의 곱이 가장 큰 { 4, 4 }가 가장 좋은 집합이다.

2. 설명

원소들의 곱이 최대가 되기 위해서는 9(4.5)의 경우와 마찬가지로 n=2일 때 최대한 중앙에 가깝게 모은 값들의 곱이 가장 큰 것을 알 수 있었다. 8의 경우(4.4). 따라서 위의 예에서 9/2를 수행하면 몫이 4가 되고, (9-4)/1을 수행하면 5가 얻어 만족을 확인한다.

n이 s보다 크면 원하는 수를 만들 수 없으므로 -1이 반환됩니다.

조건이 n > 0이면 wild 문이 실행되었습니다.

먼저 s/n 값을 입력합니다. 그 다음 나는 내가 누른 만큼 s를 빼고 나머지 계산을 하기 위해 n–를 주었다.

3. 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) {
    vector<int> answer;
    
    if(n>s){
        answer.push_back(-1);
        return answer;
    }
    
    while(n>0){
        answer.push_back(s/n);
        s-=s/n;
        n--;
    }
    
    return answer;
}