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

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

프로그래머스

 간단한 문제다. 코딩테스트 1번이 딱 이정도로 나오는 느낌. 다만 처음 읽으면 어떻게 해야할지 감이 안잡힐 수 있다. 먼저 최고의 집합이 되려면 N개의 숫자의 합이 S가 되어야한다. 즉 N개의 숫자들은 N이 3이라고하면 (N-2, 1, 1), (N-3, 1, 2) ... 이런식으로 매우 많다. 그리고 두번째 조건인 곱했을 때 최대가 되게 하려면 각 원소들간의 차이가 없어야한다.

 

즉 원소들은 (S / N, S / N . . .) 형태를 만족하며 나머지를 각 자릿수마다 1씩 더해주면 최고의 집합이된다.

이 문제를 완전탐색으로 하려하면 시간초과가 날것이다.

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

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

    int temp = s / n;
    int tmp = s % n;
    if(temp < 1)
        answer.push_back(-1);
    
    else{
    for(int i = 0; i < n; i++)
        answer.push_back(temp);
    int idx = 0;
    while(tmp > 0){
        answer[idx]++;
        idx++;
        tmp--;
    }
        sort(answer.begin(), answer.end());
    }
    return answer;
}