[C/C++] 백준 - 14606번 : 피자(Small)

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

14606번: 피자 (Small)

문제

< Picture: Designed by Kstudio / Freepik >

갑은 아주대학교 학생입니다. 갑은 팔달관 1층에서 학과 개강총회를 준비하고 있습니다. 갑은 피자를 N 판 시켰습니다. 식탁 위에 피자 N 판이 탑처럼 쌓여있습니다. 갑은 높이가 N 인 이 한 피자탑을, 높이가 1인 피자탑들로 분리시켜야 합니다. 갑은 이 일을 하기 싫었습니다. 하지만 다음과 같은 격언이 있습니다.

“피할 수 없다면 즐겨라!” - 로버트 엘리어트

격언대로, 갑은 혼자 놀기를 하며 즐겁게 일을 해결하기로 합니다. 그래서 다음과 같은 놀이를 하기로 했습니다. 

먼저 놀이를 시작하기 전에, 식탁 위엔 N 개의 피자판이 하나의 탑으로 쌓여있습니다. 놀이가 시작되면, 갑은 식탁 위에 있는 피자탑들 중 하나를 고릅니다. 그리고 고른 피자탑을 두 개의 피자탑으로 분리합니다. 이때 갑은, 분리된 두 피자탑의 높이의 곱만큼 즐거움을 느낍니다. 즉, 갑이 고른 피자탑의 높이가 A이고, 갑이 이 피자탑을 높이 B인 피자탑과 높이 C인 피자탑으로 분리했다면, 갑은 이때 B * C만큼의 즐거움을 느낍니다. 단, 높이가 1인 피자탑은 더는 분리시키지 않습니다. 갑은 계속 피자탑들을 분리해나갑니다. 이 놀이를 하다가 식탁 위에 더 이상 분리할 수 있는 피자탑이 없어진다면, 갑의 개강총회 준비 일은 끝나게 됩니다. 

갑은 문득, 혼자 놀기를 통해 얼마나 재밌게 놀 수 있을지 궁금해졌습니다. 갑이 주문한 피자판의 수 N 이 주어질 때, 갑이 혼자 놀기를 통해 얻을 수 있는 즐거움의 총합의 최댓값을 구해주세요.

< 높이가 8인 피자탑을 높이가 4인 피자탑 둘로 분리시키는 과정 >

 

1. 초기에 주어지는 피자를 나눌 수 있는 모든 방법으로 나누어보는 재귀함수 방식으로 코드를 짜본다.

ex) 5 -> (4,1), (3,2), (2,3), (1,4) ---> 단 앞에 2개와 뒤 2개는 순서만 다를 뿐 같은 수를 반환하는 것을 인지

2. 위 방식으로 재귀함수를 짜게 되면 결국 나누었던 방법을 계속해서 나누는 경우가 존재하므로 메모이제이션을 적용하여 시간을 단축시켜준다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define ENDL cout << endl
#define ll long long
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000007
#define endl '\n'

using namespace std;

int N;
int cache[11][11];

int solution(int a, int b) {
	if (a == 0) return 0;
	int& ret = cache[a][b];
	if (ret != -1) return ret;
	ret = 0;
	for (int i = 1; i <= a; i++) {
		ret = max(ret, solution(a - i, i) + a * b);
	}
	return ret;
}

void input() {
	cin >> N;
	memset(cache, -1, sizeof(cache));
}

int main() {
	fastio;
	input();
	cout << solution(N, 0) << endl;

	return 0;
}