[백준] 1500번 최대 곱

💡문제접근

• S와 K가 주어졌을 때, 합이 S이면서 배열의 원소의 곱이 최대가 되도록 해야한다. 이 때 정렬을 이용하면 수월하게 해결할 수 있다.

💡코드(메모리 : 31256KB, 시간 : 64ms)

import sys
input = sys.stdin.readline

S, K = map(int, input().strip().split())
arr = [S // K for i in range(K)]

while True:
    if sum(arr) == S:
        break
    else:
        arr[-1] += 1
        arr.sort(reverse = True)

# 내림차순 정렬을 수행해준 이유
# ex. 13 8
# [2, 2, 2, 2, 2, 1, 1, 1]
# 최대 곱 : 32

# 만약 정렬을 하지 않고 맨 뒤의 값만 1씩 늘려나간다면
# ex. 13 8
# [1, 1, 1, 1, 1, 1, 1, 6]
# 최대 곱 : 6

# 1과 곱하게 된다면 자기자신이 나오므로 최대가 나올 수 없다.
# 따라서 골고루 더해줘서 1이 최대한 안 나오게끔 수를 만들어줘야한다.
result = 1
for i in arr:
    result *= i
print(result)

💡소요시간 : 11m