프로그래머스 - 최고의 집합(Lv.3)

문제풀이

• 가능한 한 큰 숫자로 많은 제곱이 이루어져야 곱이 최대가 될 것이라고 생각했다.
• (n-1)X(n-2)X(n-3)X … 와 같이 감소하는 항이 곱해지는 경우 n^2 보다 항상 작은 결과만 얻게 된다.
• 따라서, 가능한 한 큰 숫자로 최대한 많은 제곱을 할 수 있도록 집합을 구성하는 것이 최고의 집합이 된다.

구현(All Pass)

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

using namespace std;

// 제곱수를 최대한 많이 만드는 방법이 곱이 최대가 되는 방법이다.
vector<int> solution(int n, int s) {
    vector<int> answer;
    
    if(n>s) 
        answer.push_back(-1);
    else {
        for(int i=0; i<n; i++)
            answer.push_back(1);
        int diff = s - n;
        int val = diff/n;
        int margin = diff%n;
        for(int i=0; i<n; i++)
            answer[i] += val;
        for(int i=0; i<margin; i++)
            answer[n-1-i] += 1;
    }
    
    // Debugging
    // for(auto ele:answer)
        // cout << ele << " ";
    // cout << endl;
    
    return answer;
}