백준 11052번(Python) : 카드 구매하기

www.acmicpc.net/problem/11052

11052번: 카드 구매하기

---

[풀이]

n이 4가 주어지면 1개짜리와 3개짜리를, 2개짜리 2개를 사서 값을 비교해야한다. 만약 n이 5라면 (1,4),(2,3),(3,2),(4,1)를 확인해야한다. dp에는 (1,1,1,1,1) 같은 경우는 이미 계산이 된 것으로 생각하면 된다.

 

[코드]

import sys
input = sys.stdin.readline


n = int(input())
dp = [0  for i in range(n+1)]
arr = [0] + list(map(int,input().split()))

for i in range(1,n+1):
    for j in range(1,i+1):
        dp[i] = max(dp[i],dp[i-j] + arr[j])
print(dp[i])