[프로그래머스] 최고의 집합 by 파이썬 (Python)

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

프로그래머스

 

난이도 

LV 3

 

 

문제 설명 

자연수 n개로 이루어진 집합이 있다.

집합 원소들의 합은 s와 동일하다.

이때 가능한 집합 중 각 원소의 곱이 최대가 되도록 하는 집합을 Return해주어야 한다.

만약 집합이 존재하지 않는 경우에는 [-1]을 Return 한다.

 

 

 

접근법

• 우선 집합이 존재하지 않는경우는 집합 원소의 수(n)가 원소의 합 (s)보다 크면 집합이 없다. (원소가 자연수이기 때문에 각 원소의 최소값은 1이므로 ) => 이때 [-1]을 Return 해준다.
• 각 원소의 곱이 최대가 될때는 각 원소가 모두 함께 될 수 있는 최대 값을 가져야 한다.

      ex) s = 9 , n = 3 일때  집합[3,3,3] 이 최대가 된다,

            s = 13, n = 3 일때  집합 [4,4,5] 이 최대가 된다.

• 해당 경우는 s를 n으로 나눈 몫들이 들어간다면 최대가 된다!
• 따라서 s를 n으로 나눈 몫을 집합에 저장하면서 해당 값을 s에서 빼고 n에서도 1씩 빼주며 n만큼 진행하면 원하는 집합이 완성된다.

 

 

코드

def solution(n, s):
    answer = []
    if s < n:
        return [-1]
    
    for i in range(n):
        answer.append(s//n)
        s -= s//n
        n -= 1
    
    
    return answer

 

---