[파이썬 알고리즘 문제풀이] - Section8 / Dynamic programming(동적계획법) - 9

동전교환

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

▣ 입력설명
첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.
각 동전의 종류는 100원을 넘지 않는다.

▣ 출력설명
첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.

▣ 입력예제 1
3
1 2 5
15

▣ 출력예제 1
3

import sys
sys.stdin = open("input.text", "rt")
# input = sys.stdin.readline

n = int(input())
coin = list(map(int, input().split()))
m = int(input()) # 거슬러 줄 금액
INF = 2424242424

dp = [INF] * (m+1)
dp[0] = 0 #0원을 거슬러 주는데 0개가 필요. 자명한건 미리 초기화하고 시작.

for i in range(len(coin)):
    for j in range(coin[i], m+1):
        dp[j] = min(dp[j], dp[j-coin[i]] + 1) #기존의 값과 현재 적용하는 코인을 사용하는 경우의 최소값 중에 더 작은 값으로 갱신해
        

print(dp[m])

🏈 코멘트

전형적인 냅색 알고리즘.

🏈 가방 문제(냅색 알고리즘)과 동일하게 적용하면 된다.

dp 테이블을 1차원으로 그려준 후에 dp[j]값이 무엇인지 생각해보자.

j원을 거슬러주는데 사용된 동전의 최소 개수를 의미한다.
최솟값을 저장하기 때문에 처음에는 가장 큰 값을 dp 테이블에 저장해놓으면 된다 !