백준 11052번 카드 구매하기

문제 링크

문제 접근

• N개의 카드팩을 구매하기 위해서 가장 마지막에 구매해야하는 카드팩에 집중
• 점화식을 세워서 가장 최대가 되개 하는 비용을 구한다.

D[N] = 카드 N개 구매하는 최대 비용 , P[i] : i번째 카트팩 비용
D[N] = max(D[N-i] + P[i])

알고리즘 종류

• 다이나믹 프로그래밍

import sys
N = int(sys.stdin.readline())
P = list(map(int , sys.stdin.readline().split()))
p = []
p.append(0)
d = [0]*(N+1)
for idx, i in enumerate(P):
  p.append(i)
# print(p)

for i in range(1,N+1):
  for j in range(1,i+1):
    tmp = d[i-j]+p[j]
    if tmp > d[i]:
      d[i] = tmp
print(d[N])

---

모범답안

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