[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층 피자탑의 즐거움을 더해줍니다. 

 

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

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

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

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

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

 

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