[Python] 효율적인 화폐구성

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.

 

입력 조건) 1. 첫째 줄에 N,M이 주어진다(1<= N <= 100, 1<= M <= 10,000)

                2. 이후의 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐의 가치는 10,000보다 작거나 같은 자연수이다.

 

출력 조건 1. 첫째 줄에 경우의 수 X를 출력한다.( 불가능할 때는 -1을 출력한다)

 

입력예시1                  입력예시2

2 15                          3 4

2                              3

3                              5

                                7

 

출력 예시1                 입력예시2

5                               -1

 

 

이 문제를 보고 다양한 생각이 들 수 있다. 문제를 읽고 5분동안은 어떻게 푸는게 좋을까 잘 생각해야한다. 이 때 생각하는 알고리즘이 가장 중요하다. 이 문제에서 내가 가장 먼저 든 생각은 바로 만약에 동전이 3원 5원짜리 있고 내가 13원을 만들려고 하면 일단 13원을 만들 최소 동전의 갯수는 min(8원을 만들 최소동전의 갯수, 10원을 만들 최소동전의 갯수) + 1 이라는 것이다. 그러면 저기 min안의 동전들을 또다시 이 점화식을 통해서 찾아나가니까 재귀로 풀자!!! 점화식 탑다운 오케이! 이렇게 생각했다. 

물론 이 방식도 좋다 하지만 어디까지나 구현하기 전에는 모른다 일단 완벽하게 구현하자!

내가 만든 코드는 다음과 같다.

모든값은 0으로 초기화하고 시작한다. 그리고 끝없이 빼다가 0보다 작아지는 경우가 생기면 10001을 반환한다.(무한을 의미)

 

하지만 다른 느낌으로도 풀 수 있다. 다음의 코드를 보자

더 짧다.. 역시 고수인가.. 보면 array에 화폐의 종류를 넣고 화폐부터 원하는 가치까지  모두 +1을 해가면서 넣고 그걸 화폐단위로 반복하면

최적의 조건이 모두 저장된다. 이 코드는 탑다운이 아니라 바텀업 방식으로 나와는 다르게 푼 방식이다. 여러번 생각하고 구조에 익숙해지자!