알고리즘 - Python / 백준 - 1500번 : 최대 곱

1500번: 최대 곱 (acmicpc.net)

1500번: 최대 곱

 

---

풀이

• S와 K가 주어졌을 때 , K개의 수를 가지고 S를 만든다. 이때의 K개의 수를 곱해서 나올 수 있는 가장 큰 수를 찾는 문제다.
• S를 K개의 수로 고르게 나누고 , 남는 나머지를 각각 K개에 될 수 있는 만큼 나눠주면 곱했을 때 가장 큰 경우가 나온다.
• 예를 들어 , S = 10 , K = 3의 경우 10을 3개로 고르게 나누므로 3 3 3이다.
• 고르게 나눈 후 나머지가 1 이므로 남는 나머지를 아무 수에다 더해주면 되고 이렇게 나오는 답은 3 3 4 = 36이다.
• 다른 예로 S = 7 , K = 2의 경우 , 7을 2개로 고르게 나누므로 3 3이다.
• 고르게 나눈 후 남는 나머지가 1 이므로 이 역시 아무 수에다 더해주면 되고 이렇게 나오는 답은 3 4 = 12 다. 

 

import sys
n,m = map(int , sys.stdin.readline().split(" "))
p = (n//m); q = (n%m); ans = 1
for _ in range(m):
    if q > 0:
        ans *= (p+1)
        q -= 1
    else:
        ans *= p
print(ans)

---