알고리즘 연습 [최고의 집합]

28 Jan 2018

알고리즘

최고의 집합

문제

자연수 N개로 이루어진 집합 중에, 각 원소의 합이 S가 되는 수의 집합은 여러 가지가 존재합니다. 최고의 집합은, 위의 조건을 만족하는 집합 중 각 원소의 곱이 최대가 되는 집합을 의미합니다. 집합 원소의 개수 n과 원소들의 합 s가 주어지면, 최고의 집합을 찾아 원소를 오름차순으로 반환해주는 bestSet 함수를 만들어 보세요. 만약 조건을 만족하는 집합이 없을 때는 배열 맨 앞에 –1을 담아 반환하면 됩니다. 예를 들어 n=3, s=13이면 [4,4,5]가 반환됩니다.
(자바는 집합이 없는 경우 크기가 1인 배열에 -1을 담아 반환해주세요.)

나의 풀이

def bestSet(n, s):         
    if s//n == 0:          
        return [-1]          
    answer = []            
    while n > 0:           
        answer.append(s//n)
        n -= 1             
        s -= answer[-1]    
    return sorted(answer)

n개만큼 나눌 수 있는 가장 큰 수들의 곱이 가장 클것이라 생각해서 이렇게 풀었다.

다른풀이

def bestSet(n, s):
    answer = []
    a = int(s/n)

    if a == 0:
        return [-1]

    b = s%n

    for i in range(n-b):
        answer.append(a)
    for i in range(b):
        answer.append(a+1)

    return answer

s/n의 몫을 가능한만큼 넣고 나머지 수만큼 1을 더해서 넣음. 시간이 덜 걸릴것 같다!