먼저 피자가 $n$판일 때 얻을 수 있는 최대 즐거움을 $f(n)$이라 하면 정의에 의해
\[
f(n) = \begin{cases}
0, & \text{if } n = 1 \\
\displaystyle \max_{1\le k\le\lfloor n/2\rfloor} [f(k) + f(n-k) + k(n-k)], & \text{if } n \ge 2
\end{cases}
\]
이라는 점화식이 나옵니다. 이걸 DP로 풀어도 되긴 하지만, 일단 $f(1)$부터 몇 개 구해보면 규칙이 보입니다.
\begin{align*}
f(1) &= 0 \\
f(2) &= 1 \\
f(3) &= 3 \\
f(4) &= 6 \\
f(5) &= 10 \\
f(6) &= 15
\end{align*}
굉장히 익숙한 수열입니다.
\[ f(n) = \frac{n(n-1)}{2} \]
증명은 수학적 귀납법으로 합니다.
- $n=1$일 때 성립합니다.
- $n=1,2,3,\cdots,a$일 때 성립한다고 가정하면 \begin{aligned} f(a+1) &= \max_{1\le k\le\lfloor(a+1)/2\rfloor} \left[ \frac{k(k-1)}{2} + \frac{(a-k+1)(a-k)}{2} + k(a-k+1) \right] \\ &= \max_{1\le k\le\lfloor(a+1)/2\rfloor} \frac{a^2 + a}{2} \\ &= \frac{(a+1)a}{2} \end{aligned} 이므로 $n=a+1$일 때에도 성립합니다.