프로그래머스: 최고의 집합

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

프로그래머스

설명

처음에는 제한 조건을 걸고 모든 집합을 구하려고 하였다.

하지만 가장 큰 원소의 곱의 합의 특징은 집합 내의 원소들의 값 차이가 크지 않다는 점이다.

따라서 원소의 합을 집합 개수로 나눈 몫을 구하고 나머지를 배열에 하나씩 넣어서 잡합 내의 원소 곱이 최대인 배열을 구할 수 있었다.

코드

class Solution {
    static int[] selected;
    static int target_n;
    static int target_s;
    public int[] solution(int n, int s) {
        int[] answer = new int[n];
        
        if(n > s) {
            answer = new int[]{-1};
            return answer;
        }
        
        int init = s / n;   // 몫
        int mod = s % n;    // 나머지
        
        for(int i = 0; i < n; i++) {
            answer[i] = init;
        }
        
        int idx = n - 1;
        for(int m = 0; m < mod; m++) {
            answer[idx]++;
            idx--;
        }
        return answer;
    }   
}