[ 프로그래머스 ] 최고의 집합

문제

---

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

풀이

---

집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어졌을 때, 각 원소의 합이 S가 되며 원소의 곱이 최대가 되는 집합을 구하는 문제로, 원소 곱을 최대로 하기 위해서는 원소들 간 비슷한 크기를 지녀야 하므로, S를 n으로 나눠 모듈러 연산을 통해 중간 값을 기준으로 나머지를 분배하여 원하는 집합을 찾는다.

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

using namespace std;

vector<int> solution(int n, int s) 
{
    vector<int> answer;
    vector<int> wrong_answer = { -1 };

    int quotinet = s / n;
    int remainder = s % n;

    if (n > s)
    {
        return wrong_answer;
    }

    for (int i = 0; i < n; i++)
    {
        answer.push_back(quotinet);
    }

    int idx = 0;
    while (remainder != 0)
    {
        answer[idx] += 1;

        if (idx == answer.size())
        {
            idx = 0;
        }

        else
        {
            idx++;
        }
        remainder--;
    }

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

    return answer;
}