[문제풀이] 최고의 집합

📢 문제

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

📢 알고리즘

구현

📢 풀이

• 조합 내 원소들이 균등할 때 그 곱이 가장 크다

  • [3, 5] 보단 [4, 4] 의 곱이 더 크다. 원소들이 고만고만할 수록 그 곱이 더 커진다. 따라서 균등하게 만들면 된다!

• 균등하게 만드는 방법 (ex. n = 4, s = 10)

  1. s / n 몫 값으로 조합의 n개를 채운다.
     👉 10 / 4 = 2 👉 [2, 2, 2, 2]
  2. 조합에 반영되지 못한 s % n 나머지 값에 해당하는 개수만큼 1씩 더해준다.
     👉 10 % 4 = 2 👉 [2, 2, 3, 3] (끝에 2개를 1씩 더해준다.)

• 💡 원소 중복이 허용되지 않으면 문제가 어려워질 것!

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) {
    if(n>s) {
        vector<int> answer(1, -1);
        return answer;
    }
    //가장 균등한 배열 만들기
    int div = s/n; //몫
    int mod = s%n; //나머지

    vector<int> answer(n, div);
    //mod개 만큼 +1씩
    int temp=1;
    int i = n-1;
    while(temp<=mod) {
        answer[i]++;
        i--;
        temp++;
    }
    
    return answer;
}

겁나 고민했는데 너무 허무해버림..

https://ansohxxn.github.io/programmers/101/