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

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

 

카드 팩의 가격이 주어졌을 때,

N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최솟값을 구하는 문제다.

 

import sys

input = sys.stdin.readline

N = int(input())

# 카드 값 얻기
card = [0] + list(map(int, input().split()))

# DP 테이블 생성
for i in range(1, N+1):
    for j in range(1, i):
        
        card[i] = min(card[i], card[j] + card[i-j]) # 카드팩 N개를 구매할 때의 가격 중 작은 값을 설정

print(card[-1])

 

 

[문제풀이]

---

 

이 문제는 규칙 찾기, 즉 다이나믹 프로그래밍을 이용해서 풀 수 있다.

 

 

카드를 1개 구매할 때부터 카드를 n개 구매했을 때까지 각각의 최솟값을 메모이제이션해나가며 문제를 푼다.

 

 

 

각 카드 k를 만드는 최솟값들을 더하면 구하고자 하는 카드 N을 만드는 값도 최솟값이 된다는 원리!

 

card[i] = min(card[i], card[j] + card[i-j])