[programmers/py] 최고의 집합

최고의 집합

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

문제 설명

• 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.

1. 각 원소의 합이 S가 되는 수의 집합
2. 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합

• 최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 return 해주세요.
• 만약 최고의 집합이 존재하지 않는 경우에 크기가 1인 1차원 배열(list, vector) 에 -1 을 채워서 return 해주세요.

문제 풀이

• 두 수의 차이가 적어야 해서 중앙 값에서 시작
• 나머지는 두 수의 차이로 볼 수 있음

import math
def solution(n, s):
    if s < n:
        return [-1]

    # 집합의 차이가 적게 해야함
    num = s // n
    rest = s % n

    answer = []
    # 크기 n 배열 만들기
    for i in range(n):
        answer.append(num)
        
    # 나머지는 수의 차이로 볼 수 있음 
    # [4,4] => [4,5]
    if rest != 0:
        for i in range(len(answer)) :
            answer[i] += 1
            rest -= 1
            if rest == 0:
                break
    answer.sort()
    return answer