문제

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

---

입력

집합의 원소의 개수 n과 모든 원소들의 합 s

---

출력

최고의 집합을 return

---

풀이

제한조건

• 최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 return 해주세요.
• 만약 최고의 집합이 존재하지 않는 경우에 크기가 1인 1차원 배열(list, vector) 에 -1 을 채워서 return 해주세요.
• 자연수의 개수 n은 1 이상 10,000 이하의 자연수입니다.
• 모든 원소들의 합 s는 1 이상, 100,000,000 이하의 자연수입니다.

접근방법

N개의 숫자를 더해서 S가 되며, N개의 숫자를 각각 곱했을때, 가장 큰 수가 나오는 집합을 찾는문제이다.
집합의 원소가 중복이 가능하다라는 것을 반드시 인지 하자.

예시로 살펴보자

n	s
2	9

입력이 위와 같이 주어질 때, 2개의 자연수를 각각 a와 b라고 해보자.

그럼 a + b = 9이고, 우리는 a * b가 최대인것을 찾으면 된다.

그렇다면 a = 9 - b 이므로, a * b = (9 - b) * b = 9b - b^2

a와 b의 차이가 작을수록 곱했을때, 큰 수가 나온다.

따라서 아래와 같은 흐름으로 코드를 작성한다.

1. S를 N으로 나눈 몫을 기준값으로 정한다.
2. 집합의 N개 원소를 1에서 구한 기준값으로 설정한다.
3. S를 N으로 나눈 나머지를 구한다.
4. 집합의 뒤쪽에서 부터 3에서 구한 나머지를 1씩 더하고,
   나머지를 1씩 감소시킨다.
   (집합의 원소는 오름차순 정렬로 반환하여야 함)

---

코드

class Solution {
    public int[] solution(int n, int s) {
        if(s<n)
            return new int[] {-1};
        
        int[] arr = new int[n];
        int base= s / n;
        int remain = s % n;
        for(int i = 0 ; i < n; ++i)
            arr[i] = base;
        
        int index = n - 1;
        while(remain > 0){
            arr[index--] += 1;
            remain -= 1;
        }
        
        return arr;
    }
}