[BOJ] 14606 피자 (Small) - C++

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

14606번: 피자 (Small)

아이디어

$n$개의 피자탑을 쪼갰을 때 가장 큰 즐거움을 얻으려면 짝수의 경우 $\frac{n}{2}$개, 홀수의 경우 $\frac{n}{2}$, $\frac{n}{2} + 1$개로 쪼개야 한다. 그리고 쪼개진 피자탑을 다시 쪼개서 $1$개가 될 때까지 얻을 수 있는 즐거움을 모두 더해주면 $n$개의 피자탑을 쪼갰을 때 얻을 수 있는 최대의 즐거움이다.

 

$n$개의 피자탑을 쪼개 얻을 수 있는 즐거움을 $A_n$이라고 하면

1. $n$이 짝수일 때 :

$$A_{n} = \big(\frac{n}{2}\big)^2 + 2A_{\frac{n}{2}}$$

2. $n$이 홀수일 때 :

$$A_{n} = \frac{n}{2}\big(\frac{n}{2} + 1\big) + A_{\frac{n}{2}} + A_{\frac{n}{2} + 1}$$

이다. dp를 통해 구현할 수 있다.

 

코드

#include <iostream>

using namespace std;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    int dp[n + 1];
    dp[0] = 0;
    dp[1] = 0;

    for (int i = 2; i <= n; i++) {
        if (i % 2 == 0)
            dp[i] = dp[i / 2] + dp[i / 2] + (i / 2) * (i / 2);
        else
            dp[i] = dp[i / 2] + dp[i / 2 + 1] + (i / 2) * (i / 2 + 1);
    }

    cout << dp[n];
}