[BEAKJOON] 백준 11052번 : 카드구매하기 - 파이썬

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

11052번: 카드 구매하기

 

 

문제 해결

 

반복문을 통해 각 카드 개수에 지불하는 최대 금액을 구해야 한다.

각각의 카드 개수를 지불하는 최대 금액과 이전 카드 지불한 최대 금액에서 + 현재 카드팩 가격을 비교하면 된다.

 

예제 입력 1을 보았을 때, 4개를 구매했을때 가장 큰 값은 5+5 이다.

=> dp[1] 은 num_list[1] 과 동일하기에 1일 것이다

=> dp[2]는 dp[1] + num_list[1] or num_list[2] 둘 중에 큰 값일 것이니 5이다.

=> dp[3]은 dp[1]+num_list[2] , dp[2]+num_list[1], num_list[3] 중 큰 값일 것으로 7이 된다.

=> dp[4]는 dp[1]+num_list[3], dp[2]+num_list[2], dp[3]+num_list[1], num_list[4] 중에 큰 값일 것이니 10이 된다.

 

점화식으로 표현한다면, dp[i]에 대해서 j는 1->i로 증가하면서, dp[i] = dp[i-j]+p[j] (j값에 따른 max 값)이다.

 

정답 코드

import sys
input = sys.stdin.readline

num = int(input())
num_list = list(map(int, input().split()))
dp = [0]*(num+1)

for i in range(1, num+1):
    for j in range(1, i+1):
        dp[i] = max(dp[i], dp[i-j]+num_list[j-1])

print(dp[num])