나의 코드
import sys
input = sys.stdin.readline
n=int(input())
p=list(map(int,input().split()))
dp=[0]*(n+1)
for i in range(1,n+1):
dp[i]=p[i-1]
for j in range(i):
if dp[j]+dp[i-j]>dp[i]:
dp[i]=dp[j]+dp[i-j]
print(dp[n])수행시간: 180ms
풀이
다이나믹 프로그래밍을 통해서 풀었다.
dp[2]는 2개카드 1개, 혹은 1개카드 2개 중 더 비싼값이다.
dp[3]는 3개카드 1개, 혹은 1,dp[2] 중 더 비싼값이다. 이는 1,1,1로 3을 만드는 경우, 1,2로 3을 만드는 경우 둘다 처리가 dp[2]에서 처리가 된다.
dp[i]는 i개카드1개, 혹은 1,dp[i-1] , dp[2],dp[i-2] ... 중가장 큰 값이다.
