コイン枚

質問する

ジュンギュが持っているコインは全部でN種類で、どれもたくさんあります.
硬貨を適当に使って、その価値の和をKにします.必要なコインの数の最大値を求めるプログラムを作成してください.

入力

第1行はNとKを与える.(1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
2行目から、N行目では昇順にコインの価値Aiが与えられる.(1≦Ai≦100000,A 1=1,i≧2の場合、AiはAi-1の倍数)

しゅつりょく

Kドルを作るのに必要なコインの数の最大値を1行目に出力します.

コード#コード#

#include <iostream>
#include <vector>
using namespace std;

int N, K;
vector<int> A;
int cnt;

void greedy(int money, int max) {
	int i;
	int m=0;
	if (money <= 0) return;
	for (i = max; i >= 0; i--) {
		m = money - A[i];
		if (m >= 0) break;
	}
	cnt++;
	greedy(m, i);

}


int main(void) {
	cin.tie(NULL);  ios::sync_with_stdio(false);
	cin >> N >> K;
	A.assign(N, 0);
	cnt = 0;

	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	greedy(K, N-1);
	cout << cnt;
}