동전의 단위가 1원, 5원, 10원, 50원, 100원, 500원이 있다고 하자.

이 금액을 이용하여 만들 수 있는 금액은 여러가지가 있다.

또한 어떤 한 금액을 만드는 방법도 여러가지가 있을 수 있다.

예를 들어, 50원을 만들기 위해서는 50원짜리 1개 또는 10원짜리 5개 5원짜리 10개 등 여러가지 방법이 있다.

서로 다른 여러 가지 동전들과 금액 M 이 주어질 때 M을 만드는 경우의 수를 구하는 프로그램을 작성하시오.

동전교환2 timer 1s memory 16MB

동전교환2 1s 16MB