카드 구매하기 풀이

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

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

 

풀이: dp[i] = dp[i-j] + p[j]라는 점화식을 알아내면 된다.

파이썬의 경우 https://fre2-dom.tistory.com/279 를 참고했다.

 

C++

 

Python

n=int(input())
inp=[0]+list(map(int,input().split()))
arr=[0]*(n+1)
for i in range(1,n+1):
	for j in range(1,i+1):
		arr[i]=max(arr[i],arr[i-j]+inp[j])
print(arr[-1])

Java