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

1.아이디어

n개의 원소들간의 차이가 거의 없으면서 합이 s일때, 각 원소의 곱이 최대가 된다. 따라서 우리가 해야할 일은 각 원소의 차이가 없으면서 합이 s를 이루는 원소들을 찾는 것이 목표다. 원소를 구하기 위한 간단한 방법으로 나눗셈이 있다. sn으로 나누면 몫과 나머지가 나온다. 몫은 여기서 하나의 원소고, 나머지는 하나의 원소에서 +1를 할 때 사용된다. 예를들어 n이 3이고 s가 17일 때, 몫은 5, 나머지는 2이다. 몫만 고려했을 때, {5,5,5}가 나온다. 여기서 하나의 원소에 대해, 나머지가 0이 될 때까지 +1연산을 하면 {6,6,5}가 된다. 이후, 문제 요구사항에 맞게 정렬을 취하면된다.

2.코드

def solution(n, s):
    p = s // n
    if p == 0: return [-1]
    q = s % n
    answer = [p] * n
    k = 0
    while q > 0:
        answer[k%n] += 1
        q -= 1
        k += 1
    
    answer.sort()
    return answer

좋은 웹페이지 즐겨찾기