프로그래머스 level3 최고의 집합 (python)

Problem

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

요약: n개의 자연수의 합이 S인 조합 중 원소의 곱이 최대인 집합 구하기

Solution

def solution(n, s):
    if n > s:
        return [-1]
    
    answer = [s//n] * n
    for i in range(s%n):
        answer[n - i - 1] += 1
    return answer

원소의 곱이 최대인 경우는 주어진 원소들의 차이가 거의 없는 경우이다.

n = 2, s = 5 인 경우에는 [1, 4] 보다 [2, 3]이 더 크다.

n = 4, s = 10인 경우에는 [2,2,3,3]이 곱이 최대인 조합이다.

즉, s를 n으로 나눈 몫을 베이스로 나머지 만큼 1을 더해주었다. 추가적인 정렬 연산을 안하기 위해 뒤에서부터 1을 더해주었다.