[백준] 16194번 문제 (카드 구매하기 2) 파이썬(Python) 풀이

import sys

n = int(input())
prices = [0] + list(map(int, input().split()))
dp = [0] + [sys.maxsize] * n
dp[1] = prices[1]

for i in range(2, n + 1):
    for j in range(1, i + 1):
        dp[i] = min(dp[i], dp[i - j] + prices[j])

print(dp[n])

 

https://honggom.tistory.com/79

[백준] 11052번 문제 (카드 구매하기) 파이썬(Python) 풀이

위 링크의 문제와 매우 유사한 문제이며 위 문제를 먼저 풀어봤으면, 금방 풀 수 있는 문제다.

 

문제는 매우 길어 읽고 이해하는데 시간은 꽤 걸리지만 문제를 이해했으면 솔루션을 금방 떠올릴 수 있다.

 

dp에 공간을 미리 할당해두고 이중 for문에서 dp[i]에 항상 최소값을 할당해주며 dp[n]까지 구하고 출력해주면 된다.

혹시 설명이 부족하다면 위 링크를 참고해주길 바란다!