BOJ 14606 피자(Small)

사용한 알고리즘

알고리즘 설명

피자를 B와 C로 나누면 BxC의 행복을 얻는다
이러한 관점에서 간단한 DP 식을 찾는다
DP(N) = max(1<=k<=N-1) { DP(i) + DP(N-i) + i * (N-i) }
크기가 1일때는 나눌수 없어 DP(1) = 0 이다.

풀이

// baekjoon 14606 yechan
#include <bits/stdc++.h>
using namespace std;

const int MAX_N=11;

int N;
int dp[MAX_N];

int dfs(int here) {
    int &ret = dp[here];
    if (ret != -1) return ret;
    ret = 0;
    for (int i=1; i<=here/2; i++)
        ret = max(ret, i*(here-i) + dfs(i) + dfs(here-i));
    return ret;
}

int main() {
    memset(dp, -1, sizeof(dp));
    dp[0] = dp[1] = 0;
    scanf("%d", &N);
    printf("%d\n", dfs(N));
    return 0;
}