[Python] 백준 11058번: 크리보드

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

11058번: 크리보드

1. dp의 값을 모두 1번의 경우 A로 출력할때만으로 초기화해준다.

2. 붙여넣기를 하려면 전체선택 + 복사가 필요하다. 현재 인덱스 기준으로 3번째 뒤부터 붙여넣기를 해주는 낮은 수부터 높은수 순으로 bottom-up 방식으로 진행해준다.

n = int(input())
dp = [i for i in range(n+1)]

for i in range(1, n-2):
    for j in range(i+3, n+1):
        dp[j] = max(dp[j], dp[i]*(j-i-1))

print(dp[n])