[Programmers] Level 3. 최고의 집합 (Python)

🔗 Problem Link

프로그래머스

---

❔Thinking

• 자연수 n개로 이루어진 중복집합 중에, 원소의 합이 S되고 그 곱이 최대인 집합('최고의 집합')을 반환한다.
• '최고의 집합'이 존재하지 않을 경우, [-1]을 반환한다.

---

💻Solution

import math
def solution(n, s):
    if n > s:
        return [-1]
    answer = []
    while n >= 1:
        num = math.ceil(s/n)
        answer.append(num)
        n -= 1
        s -= num
    return sorted(answer)

---

🗝️keypoint

1. 문제의 핵심을 파악하면, 해당되는 중복집합을 모두 구하지 않고도 문제를 해결할 수 있다.
2. 합이 S인 원소들의 곱이 최대이려면, 해당 집합의 모든 원소가 S를 골고루 나누어 가져야 한다.
3. S가 9 일때, {1,1,8}, {2,2,5}보다 {3,3,3}의 곱이 더 크다
4. math.ceil()은 반올림을 취해 반환한다.