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

문제

• 자연수 N개로 이뤄진 중복 집합 중 최고의 집합 리턴하기
  1) 각 원소의 합이 S가 되는 수의 집합
  2) 위 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합
• 예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있다.
  { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }
  그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합이 된다.

 

• 1 <= N <= 10,000
• 1 <= S <= 100,000,000
• 최고의 집합은 오름차순으로 정렬해 리턴하기
• 만약 최고의 집합이 존재하지 않는 경우 [-1] 리턴하기

 

풀이

• 최대한 비슷하게 나누는 것이 곱이 최대가 된다.
• 합이 s가 될 수 없는 경우를 제외하고, N개로 비슷하게 쪼개기

 

from collections import defaultdict

def solution(n, s):
    # 합이 s가 될 수 없는 경우 (예외 처리)
    if s < n :
        return [-1]
    
    # s를 n개로 쪼개기
    remains = s % n
    numbers = [s//n]*(n-s%n) + [s//n+1]*(s%n)
    
    return numbers

 

References

• 프로그래머스 Lv3