DP: 백준 11052 파이썬 카드 구매하기

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

11052번: 카드 구매하기

 

풀이:

카드 n개를 구매하면서 가장 비싸게 구매하는 금액을 출력하는 문제이다.

각 경우를 생각해보자.

 

카드 1개 살 때:

0 + 1

 

카드 2개 살 때:

0 + 2

1 + 1

 

카드 3개 살 때:

0 + 3

1 + 2

 

카드 4개 살 때;

0 + 4

2 + 2

1 + 3

 

금액 들을 dp 배열에 저장하고 배열의 최댓값을 출력해주면 된다.

 

정답:

import sys
input = sys.stdin.readline

n = int(input())
arr = [0] + list(map(int, input().split()))
# 필요한 카드의 개수가 n일 때의 최대가격 저장
dp = [0] * (n+1)

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)

print(dp[n])