[백준][파이썬] 1500번 : 최대 곱(코드, 해설, 풀이)

https://www.acmicpc.net/problem/1500

1500번: 최대 곱

 

 

 

---

- 문제

  처음 입력받은 10을 어떻게 3개로 나누어야 최대 곱이 나올지 고민하는 문제이다. 10을 1, 1, 8로 나눌수도 있고 2, 2, 6로 나눌수도 있으며 3, 3, 4 이외에도 여러가지 방법으로 나눌 수 있는데, 이때 3, 3, 4처럼 최대의 곱을 보이는 숫자를 고르면 된다.

---

- 해설

  S와 K가 10 1일 경우와 10 10일 경우에는 고민할 필요도 없이 10 한 개와 1 열 개로 나누면 되므로 문제가 될 것이 없다. 이제 나머지의 경우 두 가지로 나눌 수 있다.

 

1. 나누었을 때 딱 맞아 떨어지는 경우(20 5은 20/5 == 4)

- 이 경우에는 4를 5번 곱한 값이 가장 큰 값이 나온다. 다른 경우도 마찬가지로 S를 K로 나누었을 때 소수점이 없는 숫자가 나온다면 해당 값을 K번 곱해주면 가장 큰 최대 값이 나온다.

 

2. 나누었을 때 딱 맞아 떨어지지 않는 경우(20 3은 20/3 ~= 6.??)

- 이 경우에는 첫 번째 예시 10 3처럼 3*3*4가 가장 큰 숫자일 것이다. 이 때 10/3을 하면 3.??가 나오므로 3과 4 이 두 수를 이용해야 한다는 것을 알 수 있다. 이때 최대값을 보이기 위해서는 3보다 4를 우선적으로 사용해야 하기 때문에 3을 곱해주되, 최대한 4를 많이 곱해주는 방식으로 진행해야 한다.

 

로 해결할 수 있을 것이다.

 

---

- 풀이

import sys
S, K = map(int, sys.stdin.readline().split())
temp = S//K
max = 1
used = 0
skipped = 0
if S/K == S//K:
    for _ in range(K):
        max *= temp
else:
    for i in range(K):
        if (K-i)*(temp+1) == S-used:
            skipped = K-i
            break
        used += temp
        max *= temp
    if skipped != 0:
        for _ in range(skipped):
            max *= (temp+1)
print(max)

if S/K == S//K의 경우는 경우 1번에 해당하고 else가 경우 2번에 해당한다. 경우 2번의 경우 S/K의 결과가 3.??라고 했을 때 3을 곱해주면서 K를 계속 줄여나간다. 이때 총 남은 값이 (K-i)*4가 성립하면 나머지는 4로 모두 곱해주면 되기 때문에 예외처리를 하도록 한다. 결국 3을 계속 곱해주면서 4로 나머지를 곱해줄 수 있는 위치를 찾는 것이 핵심이다.