백준 14606번: 피자 (Small) (C++)

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

14606번: 피자 (Small)

---

Solved By: DP

 

cache 배열에다가 n층일 때, 가지는 즐거움의 총합을 넣을 겁니다.

n을 어떻게 나누었을 때, 그 두 값이 최댓값이 되는지는 몇 개만 테스트해봐도 반으로 나누었을 때가 최댓값인 게 나타납니다.

즉, 점화식은 다음과 같이 나타날 수 있습니다.

int v = i / 2; // 반으로 나누었을 때, 서로의 곱이 가장 크다.
cache[i] = (v * (i - v)) + cache[v] + cache[i - v];

 

#include <iostream>
using namespace std;

int n;
int cache[11];

int main() {
    cache[1] = 0;
    cache[2] = 1;
	cin >> n;
	for(int i = 3; i <= n; i++){
	    int v = i / 2; // 반으로 나누었을 때, 서로의 곱이 가장 크다.
	    cache[i] = (v * (i - v)) + cache[v] + cache[i - v];
	}
	
	cout << cache[n];
	return 0;
}