프로그래머스 : 최고의 집합

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

프로그래머스

 

괜히 어렵게 dfs로 풀었다가... 다시 생각했다!

 

최고의 집합의 조건을 달성하는 조건을 잘 생각해보면...

 

만약 s = 13, n = 3이라고 하면

[1 1 11] => 11

[1 2 10] => 20

[1 3 9] => 27

[1 4 8] => 32

[1 5 7] => 35

[1 6 6] => 36

[2 2 9] => 36

[2 3 8] => 48

[2 4 7] => 56

[2 5 6] => 60

[3 3 7] => 63

[3 4 6] => 72

[3 5 5] => 75

[4 4 5] => 80

이러한 경우의 수가 있고, 최고의 조합은 [4 4 5]가 된다.

 

규칙은!! 바로바로 각 원소들이 최대한 비슷한 숫자들로 이루어져 있을때가 최고의 조합이 된다는걸 알 수 있다.

 

그러니까 s/n 을 여러번 해서 조합에 넣어주기만 하면 해결되는 간단한 문제였다.

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;



vector<int> solution(int n, int s) {
    vector<int> answer;
    
    int size = n;
    
    for(int i = 0; i<size; i++){
        int num = s / n;
        if(num == 0){
            break;
        }
        answer.push_back(num);
        s -= num;
        n--;
    }
    
    if(answer.empty()){
        answer.push_back(-1);
    }
    
    
    
    
    return answer;
}