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

프로그래머스

코드

def solution(n, s):
    answer  = []
    if s > n:
        answer= [s//n for _ in range(n)]
        total = sum(answer)
        idx = n-1
        while True:
            if total == s:
                return answer
            else:
                answer[idx] += 1
                total += 1
                idx -= 1 
    else:
        return [-1]

각 원소의 곱이 최대가 되려면 원소들끼리의 차이가 적어야 한다. 

그래서 s를 n으로 나눈 몫을 n개만큼 배열에 넣어놓고 마지막 인덱스의 값부터 1씩 증가시키며 answer배열의 원소들의 합이 s와 같아지는 때를 찾는다. 이때 합을 따로 저장하지 않고 매번 sum 함수로 answer 배열의 원소들의 합을 구해주면 시간초과 발생하니 배열의 원소들의 합은 따로 정수로 저장해주어야 한다. 어차피 한 번 while문 돌릴 때마다 total 값은 1씩만 증가하므로 계산도 쉽다.

이때 주의할 점은 s보다 n이 크다면 자연수 n개의 합으로는 s를 만들 수 없으니 이 경우에는 [-1]을 리턴해주도록 하여야 한다.