[Lv3] 최고의 집합

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

자연수 n 개로 이루어진 집합 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.

1. 각 원소의 합이 S가 되는 수의 집합
2. 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합

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

집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요.

제한사항

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

---

입출력 예

n	s	result
2	9	[4, 5]
2	1	[-1]

 

입출력 예 설명

입출력 예#1
문제의 예시와 같습니다.

입출력 예#2
자연수 2개를 가지고는 합이 1인 집합을 만들 수 없습니다. 따라서 -1이 들어있는 배열을 반환합니다.

 

 

---

 

예시가 적고 설명이 누락되어있지만.. 서로 다른 수로 이루어진 집합일 필요는 없습니다. 중복이 있어도 됩니다.

 

요소들의 총합이 같은 상태에서, 같은 갯수의 수들이고, 곱이 커지려면 크기가 균등하게 큰 편이어야 합니다.

 

총 25가 될 수 있는 3개의 수 중에서,

 

[1,1,23]→23 (한 수를 극단적으로 키운 경우)

[3,4,18]→216 (1이 섞여서 못 미더운까봐 그래도 한 수를 극단적으로 키운 경우)

[3,8,14]→336 (약간 차이가 나는 경우)

[8,8,9]→576 (세 수가 거의 균등한 경우)

 

을 확인할 수 있습니다.

 

총합 s를 n개 수로 표현하려면, s를 n으로 나눈 수들을 나열하고,

 

나머지가 있다면 균등하게 1씩 더해주면 됩니다.(나머지니까 어차피 n개 까지 다 도달하지 못합니다.)

 

[a,a,a,a,a,a+1,a+1,a+1,a+1] 처럼 되겠죠.

 

 

처음에 중복이 안되는 줄 알고 풀었는데, 중복이어야 답이 나와서 더 쉬워진 문제..;;

음.. 사실 왜 level3인지 모르겠는 문제..ㅎ;

 

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