[프로그래머스] Lv2. 최고의 집합

🔗

풀이

합이 S가 되면서 곱해서 최대가 될 수 있는 수의 집합(중복 가능)

곱해서 최대가 되려면 무조건 큰 수가 많을 수록 좋을 것 같다. S=8이라고 생각해보자. 더해서 8이 되면서 가장 큰 수를 가질 수 있는 경우의 수는 (1, 7)이다. 하지만 둘을 곱하면 1이 너무 작기 때문에 7이 될 수 밖에 없다.

결국은 한쪽만 너무 커서는 소용이 없다. n개의 숫자들이 균형을 이뤄야 한다. 중복도 포함이기 때문에 여러 개가 같은 숫자일 수도 있다. 더해서 S라는 숫자가 되는 n개의 숫자 집합이 비슷비슷한 값을 갖기 위해서는 그 몫이 되는 값에 가까울 수록 유리할 것이다. S = 8이고, n = 4라면 {2, 2, 2, 2}일 때 최대의 곱을 가지게 된다.

하지만 만약 나눠 떨어지지 않는 숫자들이라면 n개보다 작은 숫자의 나머지가 남게 되는데 그럴 땐 그냥 각 숫자들에 1씩 더해주면 된다. 최대 1만 더해줘야 하는 이유는 앞서 설명했듯이 어느 하나만 큰 값을 가지는 걸로는 곱해서 최대값을 가지는 집합을 구할 수 없기 때문이다. 모두가 균일하게 적당히 큰 값을 가져야 한다.

전체 집합의 개수는 n개이다. 나눠 떨어지지 않는 상황을 가정하면 나머지의 수만큼 1을 더해주기 때문에 n개 중에 s%n(나머지)개는 s//n(몫)+1의 값을 가질 것이다. s%n을 제외한 값은 s//n(몫)의 값을 가지게 된다.

def solution(n, s):
    if not s // n:
        return [-1]
    
    ans = [s//n]*(n-s%n) + [s//n+1]*(s%n)
    return ans