백준 14606 피자

import sys

n=int(sys.stdin.readline().rstrip())
v=[0]*11
v[1]=0
v[2]=1
v[3]=3
for i in range(4,11):
    result=0
    for j in range(i//2+1):
        result=max(result,v[j]+v[i-j]+(j*(i-j)))
    v[i]=result
print(v[n])

나올 수 있는 모든 조합을 고려해야하니까 이렇게 풀었는데 찾아보니 진짜 푸는 방법이 여러개였다.

근데 제일 이해가 안되는건

dp[i] = dp[i-1] + (i-1)

이게 점화식이라는거다.

 

그래서 gpt를 써봤다

수학적으로 모든 분할이 동일하다고 한다...

예를 들어 9를 6과 3으로 나누면

18+dp[6]+dp[3]인데 이는 18+15+3 = 36이고

9를 4와 5로 분할하면

20+6+10으로 36이 된다.

 

엄청 헷갈린다...