[BOJ] 14606번 피자

www.acmicpc.net/problem/14606

14606번: 피자 (Small)

입력이 10까지 밖에 없습니다. 간단한 문제입니다. 

채점시 방법은 보지 않고 출력 결과만 보기 때문에, 이처럼 간단한 문제는 결과를 직접 배열에 저장해놓고 입력에 따라 출력하는 방법을 쓸 수도 있겠습니다.

 

[코드 보기]

#include <iostream>
using namespace std;

int main()
{
	int n;
	int dp[100] = { 0,0,1,3,6,10};
	cin >> n;
	for (int i = 6; i <= 10; i++)
	{
		int left = i / 2, right = i - left;
		int memorize = left * right;
		memorize += dp[left] + dp[right];
		dp[i] = memorize;
	}
	cout << dp[n];
	return 0;
}

[설명 보기]

1층 피자탑의 즐거움은 0입니다.

2층 피자탑의 즐거움은 1입니다.

3층 피자탑의 즐거움은 3입니다.

4층 피자탑은, 1+3의 피자탑으로 나눌 수 있고, 이때의 즐거움은 1*3=3입니다. 3층의 피자탑을 나누려고 봤더니.. 우리는 이미 3층 피자탑의 최대 즐거움을 알고 있습니다. 3에다가 3층 피자탑의 즐거움을 더해줍니다. 

 

나머지에 대해서도 같은 과정을 반복합니다.