효율적인 화폐 구성
-
[이코테 다이나믹 프로그래밍] 효율적인 화폐 구성Coding Test/이것이 코딩 테스트다 2021. 1. 10. 05:05
# 문제 N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다. # 입력 첫째 줄에 N, M이 주어진다. (1