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

16194번: 카드 구매하기 2

 

www.acmicpc.net

이 문제는 카드 i개(1 <= i <= N)가 들은 카드팩의 가격이 주어질 때 카드 N개를 구매하기 위해 드는 비용의 최솟값을 구하는 문제이다.

이를 해결하기 위해서는 dynamic programming을 이용하면 된다. 우선 길이가 N+1인 배열 dp를 만들고, dp[0]은 0으로 한다. 여기서 dp[i]는 i개의 카드를 구매하는데 드는 비용의 최솟값을 저장한다. 그러므로 초기값으로는 INF를 부여하고, dp[0]은 0으로 한다.

그리고 각 카드팩에 대해 순회하는데, i개의 카드가 든 카드팩에 대해 이전까지 추가한 카드팩을 이용해 j개의 카드를 만든 비용의 최솟값 dp[j]와, i개의 카드가 든 카드팩을 추가해 j개의 카드를 만든 경우 드는 비용 dp[j-i] + p를 비교해 더 작은 값을 dp[j]로 한다. 이때 i개의 카드가 든 카드팩을 여러 개 사용하는 경우를 고려하기 위해 j를 순회할 때 i부터 N까지 오름차순으로 순회한다.

이를 코드로 구현하면 다음과 같다.

import sys
N = int(input())
price = list(map(int, input().split()))
dp = [sys.maxsize for _ in range(N+1)]
dp[0] = 0
for i in range(1, len(price)+1):
    p = price[i-1]
    for j in range(i, N+1):
        dp[j] = min(dp[j], dp[j-i] + p)
print(dp[N])