백준 11052번(카드 구매하기) 파이썬

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

이 문제는 DP 문제이다.

점화식만 구하면 쉽게 풀 수 있는 문제이다.

그러나...

점화식 구하는게 쉽지가 않다...

점화식을 못구하겠어서 결국 챗 GPT한테 물어봤는데 친절하게 설명해줬다;;

DP는 진짜 점화식 구하는게 관건이다. 

 

n = int(input())
price = list(map(int,input().split()))
dp = [0]*(n+1)

for i in range(1,n+1):
    tmp = []
    for j in range(1,i+1):
        dp[i] = price[j-1]+dp[i-j] # 점화식!!
        tmp.append(dp[i])
    dp[i]=max(tmp)
print(dp[n])