[BOJ/백준 14606][C++] 피자 (Small)

문제

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

백준 14606

백준 14606

백준 14606

 

문제 내용

피자판의 탑을 분리하며 얻을 수 있는 즐거움의 최대치를 출력하는 것이다.

높이가 A인 탑을 높이가 B와 C인 탑으로 분리했다면, 이때 얻을 수 있는 즐거움의 크기는 B*C이다.

 

문제 풀이

일단, 높이가 A인 탑을 분리하여 가장 큰 즐거움을 얻기 위해서는, 분리하는 두 탑의 높이가 같거나 높이가 1 차이여야 한다.

ex) 7 => (1,6) (2,5) (3,4) => (3,4)로 나눌 때가 가장 값이 커진다.

ex) 6 => (1,5) (2,4) (3,3) => (3,3)으로 나눌 때가 가장 값이 커진다.

 

이 문제는 탑을 계속해서 나누어가야 하므로 dp를 이용하는 것이 좋다.

먼저, dp[1]=0, dp[2]=1이다.

피자판이 1개이면 나눌 것이 없으니 즐거움이 0이고, 피자판이 2개이면 (1,1)로 밖에 나눌 수 없으니 즐거움이 1이다.

 

그렇다면 그 이후는 어떻게 계산할까?

dp[3]= (2*1) + dp[2] +dp[1] 과 같이 계산하면 된다.

구하고자 하는 값이 dp[i]라면, i를 2로 나누어 어떻게 탑을 나눌지를 정한다.

그러고 해당 즐거움을 계산하면 (i/2) * (i - i/2)가 된다.

이후 탑을 계속해서 나누어 가므로, 이전에 계산해둔 값을 더하면 된다.(dp[i/2], dp[i - i/2]) 

 

코드

#include <iostream>
using namespace std;

int dp[11] = { 0, };
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	int n; cin >> n;
	
	//문제 해결
	dp[1] = 0;
	dp[2] = 1;
	
	//dp[3] = (2 * 1) + dp[2] + dp[1];
	
	for (int i = 3; i <= n; i++) {
		int div = i / 2;
		dp[i] = (div * (i - div)) + dp[div] + dp[i - div];
	}

	cout << dp[n] << '\n';
}