문제
동전의 단위가 1원, 5원, 10원, 50원, 100원, 500원이 있다고 하자.
이 금액을 이용하여 만들 수 있는 금액은 여러가지가 있다.
또한 어떤 한 금액을 만드는 방법도 여러가지가 있을 수 있다.
예를 들어, 50원을 만들기 위해서는 50원짜리 1개 또는 10원짜리 5개 5원짜리 10개 등 여러가지 방법이 있다.
서로 다른 여러 가지 동전들과 금액 M 이 주어질 때 M을 만드는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫 째 행 동전의 가지 수 N (1 ≤ N ≤ 20 )이 주어진다.
두번째 줄에는 N 가지 동전의 각 금액이 오름차순으로 주어진다.
각 금액은 1부터 10,000까지의 정수이다.
세 번째 줄에는 주어진 동전으로 만들어야 할 금액 M (1 ≤ M ≤ 10,000)이 주어진다.
출력
출력은 정확히 한 줄로 주어진다.
여기에 주어진 N 가지 동전으로 금액 M 을 만드는 모든 방법의 수를 출력한다.
※ M이 특정자료형 범위 이내의 수라는 생각은 위험할 수 있다. !!!
예제
3
1 5 10
100
121
출처
comkiwer
로그인해야 코드를 작성할 수 있어요.