> 문제 <

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

> 아이디어 <

dp[3] = 버튼 3번 눌렀을 때의 A의 최대 갯수

n=5 )
AA선복붙 == AAAA (n=6까지는 방법1만 쓰는게 최댓값)

n=7 )
AAA선복붙붙 = AAAAAAAAA = 9
AA선복붙붙붙 = AAAAAAAA = 8

가능한 경우의 수
1. 마지막으로 1번 버튼 누른 경우
2. 선복붙 (2,3,4)
3. 선복붙붙 (2,3,4,4)
4. 2,3,4,4,4 ... (k번)

점화식
1. dp[i] = dp[i-1]+1
2. dp[i] = dp[i-3]2 (2배)
3. dp[i] = dp[i-4]3 (3배)
4. dp[i] = dp[i-(k+2)]*(k+1)

dp[i] = max(dp[i-1]+1, dp[i-(k+2)]*(k+1)) (단, 1 <= k <= (i-3))

> 코드 <

import sys
input = lambda: sys.stdin.readline()

n = int(input())
dp=[0]*101

for i in range(7):
  dp[i] = i;     # 6까지는 방법 1(출력)이 최댓값이므로 설정

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

print(dp[n])