[Progremmers]LV.3 최고의 집합

 

---

📝풀이

해당 문제는 기본 아이디어를 세우는 게 중요하다.

1.  자연수 S를 자연수 집합 N개로 나눠야한다.
2.  집합 N개로 나눈 경우의 수 중에 곱이 가장 큰 것을 구하라

이 두개를 잘 보면 쉽게 구할 수 있다. 그건 바로 집합 N개로 나눌 때 곱이 가장 큰 것은 집합이 가장 균등해야 가능하다.

 

즉 n = 3 s = 10이면 균등 값은 [3, 3, 4]여야 한다.

 

가장 쉽게 식을 세우면 s / n만으로 모든 집합 값을 결정할 수 있다.

class Solution {
    public int[] solution(int n, int s) {
        int[] answer = new int[n];
        // n보다 s가 작으면 집합으로 못나눔
        if(n > s)
            return new int[]{-1};
        
        int idx = 0;
        while(n > 0){
            int num = s / n;
            answer[idx++] = num;
            s -= num;
            n--;
        }
        return answer;
    }
}

//1. 최고의 곱이 나오는 조건은 더했을때 균등한 값들로 더하는 것이라 생각
//2. 자연수 S를 N으로 나누고 하면 되지 않을까??