[Seop's의 코드풀이] 프로그래머스 최고의 집합 - Python

 

programmers.co.kr/learn/courses/30/lessons/12938

코딩테스트 연습 - 최고의 집합

 

문제요약

이번에 풀어볼 '최고의 집합'이란 문제는 s 라는 자연수를 n개의 자연수를 더해서 만드는 문제이다.  

그 중에서 각각의 자연수의 곱이 가장 큰 경우를 찾는것이다. 그냥 단순하게 생각하더라도 모든 경우를 고려한다면 시간이 너무 오래 걸린다는 것을 알 수 있다. 그래서 n개의 자연수 중 합이 s면서 곱이 가장 크게될 값을 한번에 찾아야 한다.  

 

문제풀이 IDEA

1. 곱이 가장 크게 되려면 유사한 값을 계속 곱하는 것이 가장 크다. 

   ex) n : 2, s : 8 이라면 [1,7] 보다 [3,5]가 더 크며 [4,4]가 가장 크다는 것을 알 수 있다.  

2. s 를 n으로 나눈 값과 나머지를 통해 가장 유사하면서 합이 s 가 되도록 진행한다.  

   ex) n: 2, s : 9 라면 값은 4, 나머지는 1이된다. 4를 기준으로 유사값들이 생성된다.

3. 나머지 값이 0이 될때 까지 값에다가 1씩 더해주며 최고의 집합을 만든다.

 

아래 사진을 보면 보다 이해가 쉬울 것이라 예상된다.  

 

코드

def solution(n, s):
    answer = []
    v, r = divmod(s, n)
    if v == 0 :
        return [-1]
    if r == 0 :
        return [v]*n
    
    for i in range(n) :
        if i < r :
            answer.append(v+1)
        else :
            answer.append(v)
    return sorted(answer)