[연습문제] 최고의 집합 - JAVA

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

프로그래머스

---

이 문제는 엄청 어렵지는 않았는데 포인트를 잡는 것이 관건이었다

전체 가능한 경우의 수를 구하는 것이 아닌, 최고의 집합을 찾는 규칙을 발견하는게 중요하였다!!

 

최고의 집합 조건은 주어진 원소의 개수만큼 주어진 합을 만족하고, 각 원소의 곱이 최댓값인 경우이다

즉, 최대 곱이 나오는 경우를 고민하는 것이 중요하다!

 

만약 n=3, s=6이면, 최고의 집합은 [2,2,2]가 된다

즉, s를 n으로 나눴을 때 나오는 수를 이용하면 된다

 

예시)

• n = 3, s = 9 -> [3, 3, 3]
• n = 2, s = 10 -> [5, 5]
• n = 4, s = 28 -> [7, 7, 7, 7]

 

이 떄 만약 s가 n으로 나눠떨어지지 않으면, 나머지를 각 원소에 배분해서 1씩 더해주면 되는것이다

예를 들어 s=10, n=3이라고 해보자

그러면 [3, 3, 4] 가 최고의 집합이 된다

즉, 나머지가 1이니까 뒤의 원소부터 1씩 더해준 것이다

 

예시)

• n=3, s=11 -> 나머지가 2이므로 뒤에서부터 2번째 원소까지 1을 더해주면 [3, 4, 4] 가 된다
• n=4, s=15 -> 나머지가 3이므로 뒤에서부터 3번째 원소까지 1을 더해주면 [3, 4, 4, 4] 가 된다

 

 

 

 

자바 코드)

import java.util.*;

class Solution {
    public int[] solution(int n, int s) {
        if (n > s) {
            return new int[]{-1};
        }

        int[] answer = new int[n];
        // 자연수 집합
        // n개의 원소, 원소의 합 = s
        // 곱이 최대가 되는 집합 반환
        for (int i = 0; i < n; i++) {
            answer[i] = s / n;
        }

        int remain = s % n;
        for (int i = n - 1; i >= n - remain; i--) {
            answer[i] += 1;
        }

        return answer;
    }
}

---

참고)

https://tosuccess.tistory.com/76

[프로그래머스 level_3] 최고의 집합 for JAVA