[java] 프로그래머스 - 최고의 집합

문제

프로그래머스-최고의 집합
자연수 n개로 이루어진 집합 중 합이 s개가 될 때, 각 원소의 곱이 최대인 집합을 구하는 문제

• 제한 사항
  최고의 집합은 오름차순으로 정렬된 1차원 배열
  최고의 집합이 존재하지 않는 경우, 크기가 1이며 -1이 채워진 배열을 리턴
  자연수의 개수 n : 1 <= n <= 10,000
  모든 원소들의 합 s : 1 <= s <= 100,000,000

• 예시
  n = 2, s = 9 일때 가능한 집합은 다음과 같다
  { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }
  이 때 원소의 곱이 가장 큰 경우는 { 4, 5 }이다

풀이

우선 합 s가 n보다 작은경우, 불가능하다
s = 3, n = 5일때 가장 작은 자연수인 1을 n번 더해도 s가 되지 않기 때문이다

우선 n개의 원소의 갯수 합이 s가되면서, 곱이 최대가 나와야 하므로
최대를 만족하는 원소의 갯수는 n개다

n개의 곱이 최대가 나오려면 각 n이 숫자가 균등하게 커야하는데
s % n == 0 이면 s / n을 n만큼 채워준다

s % n != 0이면 그 나머지만큼 s/n + 1을 해준다
이 때, 정답의 뒤에서부터 추가해야한다
(오름차순 조건이 있기 때문)

소스코드

import java.util.*;
class Solution {
 static int[] answer;

	public int[] solution(int n, int s) {
		if (s < n) {
			answer = new int[1];
			answer[0] = -1;
			return answer;
		}
		answer = new int[n];
		if (s % n == 0) {
			for (int i = 0; i < answer.length; i++) {
				answer[i] = s / n;
			}
		} else {
			int m = s / n;
			int last = s % n;
			for (int i = answer.length - 1; i > -1; i--) {
				if (last > 0) {
					answer[i] = m + 1;
					last--;
				} else {
					answer[i] = m;
				}
			}

		}
		return answer;
	}

}