[BOJ] 피자 (Small)

DP를 너무 못하는 관계로 쉬운 DP부터 차근차근 익숙해지려고 한다.
피자(Small)

해당 문제는, $N$ 높이를 가진 피자 탑을 쪼개면서 최대 즐거움을 찾는 문제이다.
두 가지로 풀었는데, 하나는 완전 탐색과 하나는 DP이다.
먼저 처음 접근한 DP 방법이다.

$N=1$일때 즐거움은 0으로 문제에서 제공했다.
그렇다면, $N=2$일때는, 하나를 떼어내면 높이 1짜리 타워 두개가 완성된다. 이 때 즐거움은 $1 \times 1 +0+0=1$이다. 1짜리 두개로 떼어냈으니 1x1, 높이1짜리의 기존 즐거움이 더해진 값이다.
$N=3$일때는, 1, 2로 떼어 낼 수 있다. 이때 즐거움은 $1\times2+0+1$ (떼어낸 두 크기인 2x1, 각각 1과 2의 즐거움인 0 + 1)이다.
이를 반복해서 쓰다보면... 같은 계산값을 반복해서 사용하게 됨을 눈치 챌 수 있다. N=3일때만 보더라도, N=2, N=1일때 계산값이 반복해서 필요해지게 된다. 따라서 DP로 접근할 수 있다.

먼저, N이 짝수일땐 무조건 반으로 쪼개는게 가장 크다. (N과 즐거움은 비례한다.)
따라서 다음 점화식을 따른다.

만약 N이 홀수라면, N을 2로 나눈 몫과, 그에 1을 더한값으로 나누는게 가장 크다.

이를 코드로 옮겨주면 된다.

arr=[0, 0]
for i in range(2, 10 +1):
    if i%2 == 0:
        arr.append((i//2)**2+arr[i//2]*2)
    else:
        arr.append(i//2 * (i//2+1) + arr[i//2] + arr[i//2+1])
print(arr[int(input())])

완전 탐색은, N이 10밖에 안되기 때문에 충분히 시간내에 풀 수 있는 선택지다.
2중 for문 변수를 i,j라고 둘 때 $i+j=N$인 케이스에서,
$dp[N] = i\times j+dp[i]+dp[j] (1<=i<= {N\over2}, i<=j<=N)$
를 적용해주면 된다.

arr=[0] * 11
for i in range(2, 10 + 1):
    for j in range(1,i//2+1):
        for k in range(j, i+1):
            if j+k > i:
                break
            if j+k == i:
                arr[i] = j*k + arr[j]+arr[k]
print(arr[int(input())])