[Algorithm] Dynamic Programming - ‘효율적인 화폐구성 문제’

📣 학습한 내용을 정리한 글입니다.

다이나믹 프로그래밍 알고리즘 문제입니다. 문제에 대한 내용과 풀이 그리고 결과를 간단하게 작성하였으니 참고바랍니다.
풀이 언어 : Python

문제 설명

---

내용

N가지 종류의 화폐가 있습니다. 이 화폐들의 개수를 최소한으로 이용해서 가치의 합이 M원이 되도록 한다.
예를 들어 2원, 3원 단위의 화폐로 15원을 만들기 위해 3원 5개를 사용하는 것이 최소한의 화폐 개수이다.
M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 N, M이 주어진다. (1 <= N <= 100, 1 <= M <= 10,000)
두 번째 줄에는 이후의 N개의 줄에는 각 화폐의 가치가 주어진다.

출력

첫째 줄에 최소 화폐의 개수가 출련된다. (단, 불가능할 때는 -1을 출력한다.)

문제 풀이

---

Dyanmic Programming Algorithm 참고내용

• 동적계획법이라고도 부르며, 최적 부분구조 및 중복되는 부분 문제의 조건에 맞게 출제된다.
  
• 통상적으로 점화식을 이용하며 bottom-up(상향식)방식으로 풀 수 있다.
  
• dp 테이블을 이용하여 점화식을 적용시켜 문제를 풀어간다.
  

위 참고사항을 준수하며, 풀어보자.
dp 테이블을 만들어 M원일 때 최소의 화폐의 개수를 얻을 수 있는 배열을 만든다.
dp[i] = 금액 i를 만들 수 있는 최소한의 화폐 개수, k = 각 화폐의 단위일 때,
점화식으로 각 화폐 단위인 k를 하나씩 확인한다.

• dp[i] = min(dp[i], dp[i-k]+1)
• else, dp[i] = INF
  
  

작성 코드

Python

---

참고 : ‘동빈나’님의 (이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍 영상

---