[백준 시리즈] 14606번 : 실버4 - 피자 (Small) / Python

제목 : 피자 (Small)

출처 : 백준 /  14606번: 피자 (Small) (acmicpc.net)

사용 알고리즘 : 다이나믹 프로그래밍

문제 설명

1. 식탁 위에 N ( 1 <= N <= 10 )개의 피자판이 하나의 탑으로 쌓여있다.

2. 식탁 위에 놓여있는 모든 피자판의 높이가 1이 될 때까지 둘로 나눈다.

3. 탑을 둘로 나누는 행위에서 나누어진 두 탑의 높이의 곱만큼 즐거움을 얻는다고 할 때, 즐거움의 총합의 최댓값을 구해라.

 

제한

시간 제한 : 1초

메모리 제한 : 512 MB

---

문제 풀이

1단계 : 최대 시간복잡도는 얼마인가?

N의 크기가 10 이하이기 때문에 시간 복잡도 제한이 없다.

 

2단계 : 하나의 케이스에 대해 답을 어떻게 구할 수 있는가?

X+Y = Z의 방정식을 가지는 X, Y에 대해서 X*Y는 X와 Y는 Z/2일 때 항상 최댓값을 가진다. 따라서, 탑을 절반으로 계속해서 나누면 즐거움의 합이 항상 최대가 될 것이다."라고 일단 가정하고 문제를 풀어본다. <예제 입력 3>에 대해 답을 구해보자. N이 5일 때, 답은 10이다. N이 5일 때, 가정에 의거하여 3x2 + (1x2 + 1x1) + (1x1) = 10 이므로 해가 구해졌다.

<예제 입력 3>

 

1) X+Y = Z 일 때, (Z/2, Z/2)에서 X*Y의 값이 항상 최대가 되는 이유
Y = Z - X
연립하여 풀면, X*Y = X(Z-X)
X에 대하여 이차함수의 개형을 가지므로, X*Y는 X = Z/2, Y = Z/2 인 지점에서 최댓값을 가진다.

 

3단계 : 2단계에서 사용한 방법을 일반화할 수 있는가?

일반화 할 수 없다. <2단계>에서는 가정이 적용되는 것처럼 보였으나, 탑을 나누는 첫 시도에서 절반으로 나누는 행위가 즐거움의 총합의 최댓값을 항상 구할 수 있다는 보장이 없다. 이렇게 되면, 탑을 나누는 각 단계에 대해 모든 경우의 수를 탐색해야 한다고 생각해볼 수 있다.

 

그러나, 어떤 탑의 높이 n에 대해, 해가 고정적이고 독립적이기 때문에, 다이나믹 프로그래밍 기법 중 Tabulation을 적용하여 문제를 풀 수 있다.

각 단계 n에 대해, dp[n] = max(dp[n], j*(i-j) + dp[j] + dp[i-j])

---

정답 코드

n = int(input())
dp = [0 for _ in range(n+1)]

for i in range(2, n+1):
    for j in range(1, i//2 + 1):
        dp[i] = max(dp[i], j*(i-j)+dp[j]+dp[i-j])

print(dp[n])

* i가 아닌 i // 2 + 1을 입력한 이유는 최적화 때문이다.

---