[lv3] 최고의 집합

 

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

s / n == 0 이라면, s를 이루는 수 중에 0이 반드시 포함되어야 함을 의미하므로 해가 아니다.

=> 모든 원소는 자연수여야 한다.

 

예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다.
{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }
그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다.

 

아니라면,

합 s를 이루는 n개의 원소의 값을 가장 가깝게 해야한다.

 

따라서, s / n 값으로 배열을 채워넣고 s % n 값 만큼 각 원소에 +1을 해준다.

 

s % n 값은 항상 n보다 작음이 보장되고, 넘어간다면 s / n의 값이 증가하고 s % n는 0부터 다시 시작한다.

=> 각 원소에 +2, +3 등을 해야 최적인 경우는 없다. 

 

class Solution {
    public int[] solution(int n, int s) {
        int[] answer = {};
        
        if(s / n < 1) {
            answer = new int[]{-1};
        }
        else {
            int val = s / n;
            int modVal = s % n;

            answer = new int[n];

            for(int i = answer.length - 1; i >= 0; i--) {
                if(modVal != 0) {
                    answer[i] = val + 1;
                    modVal--;
                }
                else {
                    answer[i] = val;
                }
            }
        }


        return answer;
    }
}