동전 교환 문제
Coddy의 다이나믹 프로그래밍 101 코스 레슨 — 15개 중 8번째.
동전 교환 문제(coin change problem)는 동적 계획법(dynamic programming)의 고전적인 문제입니다. 서로 다른 액면가를 가진 동전 세트와 총 금액이 주어졌을 때, 주어진 금액을 만드는 데 필요한 최소 동전 개수를 찾는 것이 과제입니다.
예를 들어, 액면가가 [1, 5, 10]인 동전이 있고 총 15라는 금액을 만들고 싶다고 가정해 봅시다. 필요한 최소 동전 개수는 2개(10원 동전 1개와 5원 동전 1개)가 됩니다.
동적 계획법을 사용하여 이 문제를 해결하기 위해, 행은 동전의 액면가를 나타내고 열은 0부터 주어진 총 금액까지의 금액을 나타내는 표를 만들 수 있습니다. 그런 다음 각 액면가의 동전을 사용하여 각 금액을 만드는 데 필요한 최소 동전 개수를 계산함으로써 상향식(bottom-up) 방식으로 표를 채워 나갑니다.
챌린지
중급두 개의 입력(동전 단위 목록과 목표 금액)을 받아, 목표 금액을 만드는 데 필요한 최소 동전 개수를 반환하는 프로그램을 작성하세요.
예를 들어, 단위가 [1, 5, 10]이고 목표 금액이 15인 경우, 출력은 2가 되어야 합니다.
직접 해보기
def min_coins(coins, target):
# 여기에 코드를 작성하세요