[백준] 16194 - 카드 구매하기 2 (파이썬)

문제 링크

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

문제 요약

민규는 N개의 카드를 구매하려고 하며, 카드가 iii개 포함된 카드팩의 가격이 P_i일 때, N개의 카드를 구매하기 위해 최소 금액을 구하고자 합니다. 카드팩은 1개에서 N개까지 다양한 크기가 있으며, 카드팩 여러 개를 조합하여 정확히 N개의 카드를 구입해야 합니다.

푼 방법

 

• DP 배열 dp[i]: i개의 카드를 구매하는 데 필요한 최소 비용을 저장하는 배열입니다.
• 초기값으로 dp[0]=0을 설정합니다. 이는 카드가 0개 필요할 때 비용이 0원임을 의미합니다.
• 점화식: dp[i]=min⁡(dp[i],dp[i−j]+P[j])
  • 카드 i개를 구매할 때, 개 들어 있는 카드팩을 사용하여 i−j개의 카드에서 최소 비용을 계산해 나갑니다.
  • 이 과정을 통해 dp[i]에는 i개의 카드를 구매하는 데 필요한 최소 비용이 누적됩니다.
• 최종적으로 dp[n]이 N개의 카드를 구매하는 최소 비용이 됩니다.

 

정답 코드

n = int(input())

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

dp=[0 for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,i+1):
        if dp[i] == 0:
            dp[i] = dp[i-j] + P[j]
        else:
            dp[i] = min(dp[i] , dp[i-j]+P[j])
print(dp[n])

배웠던 부분

동적 계획법 (Dynamic Programming): 전체 문제를 더 작은 하위 문제로 나누어 풀고, 각 하위 문제의 최적해를 활용하여 전체 문제의 최적해를 구하는 방식입니다.

• 이 문제에서는 하위 문제로서 "카드 i개를 구매하는 최소 비용"을 설정하고, 이를 기반으로 더 큰 문제를 해결해 나갑니다.