99. 동전교환(냅색 알고리즘) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★☆☆☆

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, a;
	cin >> n;
	vector<int> C;
	
	for(int i = 0; i < n; i++)
	{
		cin >> a;
		C.push_back(a);
	}
	
	cin >> m;
	
	vector<int> V(m+1, 0);
	
	for(int i = 0; i < C.size(); i++)
	{
		for(int j = 0; j < V.size(); j++)
		{	
			if(j - C[i] < 0) continue;
			
			if(V[j] > V[j-C[i]] + 1 || V[j] == 0)
				V[j] = V[j-C[i]] + 1;
		}
	}

	cout << V[m] << "\n";
	
	return 0;
}