백준 11502 카드 구매하기

haruponea·2021년 4월 5일
0

BOJ

목록 보기
38/41

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

풀이
생각보다 쉬운 문제였습니다. dp[i]를 카드 i개를 구매했을때 금액의 최댓값이라고 정의하면 점화식은 다음과 같습니다.
dp[i] = max(dp[i-j] + dp[j], dp[i]) 0 <= j < i
dp[i]의 초기화는 price[i]로 하면 됩니다.

python

import sys
input = sys.stdin.readline
n = int(input())
price = [0]
l = list(map(int,input().split()))
for p in l:
    price.append(p)
dp = [0]*(n+1)
dp[1] = price[1]
for i in range(2, n + 1):
    dp[i] = price[i]
    for j in range(i):
        dp[i] = max(dp[i-j] + dp[j], dp[i])
print(dp[n])

0개의 댓글