[백준-11058] 크리보드

풀이

1~6까지는 그냥 A를출력하는 버튼을 그 숫자만큼 누르는게 복사해서 붙여넣기하는 것보다 더 많거나 같다.
7부터는 무조건 붙여넣기 하는게 더 많아지고 붙여넣기를 1~3번한 것중 답이있다.
(왜 1~3번중에 답이 있는지는 잘 모르겠다.)
따라서 dp[i]=max(dp[i-3]*2,dp[i-4]*3,dp[i-5]*4)

코드

import sys
input = sys.stdin.readline
n=int(input())
dp=[i for i in range(n+2)]
buffer=0
for i in range(7,n+1):
    dp[i]=max(dp[i-3]*2,dp[i-4]*3,dp[i-5]*4)
print(dp[n])

수행시간 : 72ms