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

카드 구매하기와 정말 비슷하다.

https://na0-0.tistory.com/126

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

 

 

문제

https://www.acmicpc.net/problem/16194

16194번: 카드 구매하기 2

 

위의 문제와 이 문제의 가장 큰 차이점은, N장의 카드를 갖기 위해서 지불해야하는 금액의 "최댓값"을 구하냐, "최솟값"을 구하냐의 차이이다. 전체적인 로직은 거의 비슷하다.

 

달라진 점으로는, dp를 입력받은 list로 수정을 해주었고,

이전 포스팅에서는 보기 편하게 1로 카운트해줬지만, 0부터 시작하게 해주었다.

 

 

 

해결 코드

import sys
input = sys.stdin.readline

num = int(input())
num_list = list(map(int, input().split()))
dp = num_list

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