프로그래머스 문제 - 최고의 집합

프로그래머스 최고의 집합 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

각 원소의 합이 s가 되는 수의 중복 집합들이 있습니다.
위 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합이 최고의 집합이 됩니다.
집합 원소의 갯수 n과 원소들의 합 s를 입력받았을 때 최고의 집합을 찾아야합니다.

문제 풀이

각 원소들의 곱이 최대가 되기 위해서는 모든 원소가 골고루 높은 수를 가져야 합니다.
그러기 위해서는 원소들의 합을 원소의 갯수로 나눠줌으로써 모든 원소가 동등하게 높은 수를 가지도록 해야 합니다.
예를 들어 n=3, s=17일 경우 s/n 즉 17/3=5 이므로 배열에는 [5, 5, 5]처럼 들어가야 합니다

하지만 모든 원소들의 합이 s와 같아야 하기 때문에 나머지 값들을 뒤에서부터 1씩 더해주면 최고의 집합이 나오게 됩니다.
즉 [5, 5, 5]배열에 s=17일 경우 나머지가 2이므로 뒤에 두 원소에 1씩 더해주면 [5, 6, 6]이 되어 최고의 집합이 됩니다.

전체 코드

이번 문제는 어떤 답을 원하는지 빠르게 알아채면 풀 수 있는 문제였습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) {
    vector<int> answer;
    int divValue, divRest;
    
    if(s < n)
    {
        answer.push_back(-1);
    }
    else
    {
        divValue = s / n;
        divRest = s % n;
        for(int i = 0; i < n; i++)
        {
            answer.push_back(divValue);
        }
        int size = answer.size();
        for(int i = 0; i < divRest; i++)
        {
            size--;
            answer[size]++;
        }
    }
    
    return answer;
}

출저

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