카드 구매하기 2 풀이

문제 링크: https://www.acmicpc.net/problem/16194

백준 알고리즘 기초 1/2 400에서 6번째 - 16194번 카드 구매하기 2를 풀어보았다.

 

풀이: 점화식은 카드 구매하기 1과 같으나, dp의 처음을 0으로 설정해 주면 된다.

 

C++

 

Python

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

Java