[백준] 16194번: 카드 구매하기 2

문제

백준 - 16194번: 카드 구매하기 2

분석

카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.
카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최솟값을 구하는 문제이다.

카드 구매하기 1과는 달리 최소를 구하는 문제이다.
i는 i개 얻은 카드 개수를 의미하고, j는 고를 수 있는 카드를 대입해 보는 과정이다.
i가 j보다 크거나 같으면 j개 이상의 카드를 얻을 때 경우고, 기존의 dp[i]와 i-j개를 얻을 때 최소 금액인 dp[i-j]에 prices[j]를 더한 값을 비교하여 더 작은 값으로 유지시킨다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

n = int(input())
prices = [0]+list(map(int, input().split()))

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

print(dp[n])

끝으로..

다이나믹 프로그래밍의 기초 문제를 풀어봤다.
DP문제를 안 푼지 조금 되어 기초를 다시 다져봐야겠다.