[Python] 프로그래머스 - 최고의 집합

프로그래머스 최고의 집합 문제는 자연수 n개로 이루어진 중복 집합 중에서 각 원소의 합이 S가 되고 각 원소의 곱이 최대가 되는 집합을 구하는 문제다. 난이도는 레벨3이며 그리디한 방식으로 해결할 수 있다.

 

프로그래머스 - 최고의 집합 문제 정보

알고리즘 분류

- 그리디

난이도

- Level 3

 

문제 요약

• 자연수 n개로 이루어진 중복 집합 중에서 각 원소의 합이 S가 되고 각 원소의 곱이 최대가 되는 집합을 최고의 집합이라고 한다.
• n, S가 주어졌을 때 최고의 집합을 구하라.

 

문제 풀이 과정

• 집합 내의 두 숫자의 차의 최댓값이 1인 경우에 곱이 최대가 된다.
• ex) n=3, S=8 → {2,3,3}
• S를 n으로 나누었을 때의 몫과 나머지를 이용하여 최고의 집합을 구할 수 있다.
  • 몫이 0이면 최고의 집합이 존재하지 않는 경우이다.
  • {몫, 몫, …, 몫+1, 몫+1}의 합이 S가 되도록 하면 된다.

코드

def solution(n, s):
    answer = []
    
    d, m = divmod(s, n)
    if d == 0:
        return [-1]
    
    for _ in range(n-m):
        answer.append(d)
    for _ in range(m):
        answer.append(d+1)
    
    return answer

• 시간복잡도: O(n)
• 공간복잡도: O(n)