카테고리 없음
[알고리즘][백준] 11052번 카드 구매하기 - 파이썬(python) 풀이
무명오리
2024. 3. 5. 18:27
https://www.acmicpc.net/problem/11052
11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
dp에 카드i장씩 살때 가장 큰 값을 넣으면 된다
점화식으로는 dp[i] = dp[i-j] + p[j]
import sys
n = int(sys.stdin.readline())
p = [0] + list(map(int, sys.stdin.readline().split()))
# [0] + 대신 p.insert(0,0)도 가능
dp = [0] * 1001
for i in range(1, n+1):
for j in range(1, i+1):
dp[i] = max(dp[i-j] + p[j], dp[i])
print(dp[n])