BOJ 14607:: 피자

http://acmicpc.net/problem/14606

http://acmicpc.net/problem/14607

제가 좋아하는 종류의 수학문제입니다.

먼저 피자가 $n$판일 때 얻을 수 있는 최대 즐거움을 $f(n)$이라고 하면 정의에 의해서

\[
f(n) =
\left \{
\begin{array}{cl}
0 & (n = 1) \\[5pt]
\displaystyle \max_{1\le k\le \lfloor n/2\rfloor} \{ f(k) + f(n-k) + k(n-k) \} & (n \ge 2)
\end{array}
\right .
\]

이라는 점화식이 나옵니다. 이걸 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} \]

증명은 수학적 귀납법으로 합니다.

  1. $n=1$일 때 성립합니다.
  2. $n=1,2,3,\cdots,a$일 때 성립한다고 가정하면

\[
\begin{align*}
f(a+1) &= \max_{1\le k\le \lfloor n/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 n/2\rfloor} \left \{ \frac{a^2+a}{2} \right \} \\
&= \frac{(a+1)a}{2}
\end{align*}
\]

이므로 $n=a+1$일 때에도 성립합니다.