어떤 나라의 화폐는 항상 가장 큰 단위가 그보다 작은 단위들의 배수가 되도록 설계되어 있어, 큰 단위부터 욕심껏 사용하는 방식으로 항상 최소 개수의 화폐를 만들 수 있다. 화폐 단위 \(N\)개가 주어질 때, 정확히 금액 \(M\)을 만드는 데 필요한 화폐의 최소 개수를 출력하여라.

단위들은 \(a_1 > a_2 > \dots > a_N\) 순으로 주어지며, 각 \(a_i\) 는 \(a_{i+1}\) 의 배수이고 \(a_N = 1\) 이다. 따라서 어떤 금액이든 항상 만들 수 있다.

• \(1 \le N \le 20\)
• \(0 \le M \le 1\,000\,000\,000\)
• \(a_1 > a_2 > \dots > a_N = 1\) 이고 각 단위는 다음 단위의 배수

첫째 줄에 화폐 단위의 수 \(N\)과 만들 금액 \(M\)이 공백으로 구분되어 주어진다.

둘째 줄에 \(N\)개의 화폐 단위가 큰 것부터 작은 것 순으로 공백으로 구분되어 주어진다.

금액 \(M\)을 만드는 데 필요한 화폐의 최소 개수를 한 줄에 출력한다.

riseoj 작성

출처 Original