[골5] 2294 - 동전2

#include <iostream>
#include <vector>

#pragma region 입출력 속도향상

#define FAST_IO() \
{\
	ios::sync_with_stdio(false);\
	cin.tie(NULL); \
	cout.tie(NULL); \
}\

#pragma endregion

using namespace std;

int main()
{
	FAST_IO();
	int n, k;
	cin >> n >> k;
	vector<int> v(n), dp(k + 1);

	for (int i = 0; i < n; i++)
		cin >> v[i];

	for (int i = 1; i <= k; i++)
		dp[i] = 10001;

	for (int i = 0; i < n; i++)
	{
		for (int j = v[i]; j <= k; j++)
			dp[j] = min(dp[j], dp[j - v[i]] + 1);
	}
	cout << (dp[k] == 10001 ? -1 : dp[k]);
	return 0;
}