[백준][Python] 16194번 카드 구매하기2

16194번: 카드 구매하기 2

 

코드

n = int(input())
p = list(map(int,input().split()))
dp = [0]*(n+1)
dp[1] = p[0]
dp[2] = min(dp[1]*2,p[1])
for i in range(3,n+1):
	dp[i] = p[i-1]
	for j in range(1,i//2+1):
		dp[i] = min(dp[i],dp[j]+dp[i-j])
print(dp[-1])