[프로그래머스/Lv.3] - 최고의 집합

문제 링크

아이디어

최고의 집합을 만족하려면, 집합을 구성하는 원소들이 가장 가깝게 인접해 있어야 한다.

코드

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

풀이

문제의 목표

• 조건을 만족하는 최고의 집합 구하기.

원소들이 가장 가깝게 인접해 있다는 것은 서로의 차가 가장 작다는 의미이다.
(ex. n=2, s=9 ➡️ [3, 6] 보다, [4, 5]가 더 가깝게 인접해있다.)

이를 만족하려면, s를 n으로 나눈 몫을 n개로 모두 공평하게 나눈다.
(ex. n=3, s=9 ➡️ [3, 3, 3])

그 후, 나머지(s % n)를 집합을 이루는 모든 원소에 대해 1씩 분배한다.(나머지가 0이 아닐 때 까지)