[프로그래머스 최고의 집합] c++ (풀이 ,코드)

문제 링크

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

프로그래머스

 

문제

 

풀이, 코드

우리가 생각을 해봅시다. 합들에 대해서 가장 큰곱을 구하는 방법에 대해서 궁금해 하실겁니다.

 

이거를 우리가 수학에 대한 지식을 가져야 하는건가? 물론 귀납적인 방법으로 몇개를 세우다보면 

아.. 가장 s와 n을 나눈것들을 기본으로 하고 s%n을 해서 그만큼 1을 더해주면 되겠구나라는 느낌이 생기긴 합니다.

 

예를 들어 4 16 이라면 4 4 4 4 일때의 최곳값이 되겠네요

문제의 예시들도 보시게 되면

ex1) 2 9 -> s/n에서 4 4 를 배정하고 s%n이 1이므로 하나를 더해줘서 5,4가 됩니다.

ex2) n>s라면 불가능합니다.

ex3) 2 8 도 같은 방식으로 4 4가 됩니다.

/*

최고의 집합

자연수 n개로 이루어진 중복집합

원소의 개수 n과 모든 원소들의 합 s

곱이 최대려면 최대한 s/n에 근접하는게 가장 최선 아닐까?

*/

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

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

    vector<int> answer;

    int sum = 0;

    int overCnt = s % n; //결국 8887 이런식이 가장 크므로 888이렇게 overCnt를 측정

   

    if(n > s){

        answer.push_back(-1);

        return answer;

    }

   

    for(int i =0;i<n;i++){

        if(i < overCnt){

            answer.push_back(s/n + 1);

        }else{

            answer.push_back(s/n);

        }

    }

   

    sort(answer.begin(),answer.end());

    return answer;

}