풀이 전략

1) 그리디로 하기에는 예외조건이 있따.

예제) 동전이 8이고, 1,4,5원이 존재할 때 최소 개수를 구할 경우
그리디로 접근하면 가장 큰 5로 나눈 후 나머지는 낮은 수로 처리를 하겠다!
라고 생각하고 접근하면 5 ( 1)+ 1 ( 3) -> 총 4개이다.

but! 최적의 개수는 4 (* 2) -> 2개이다.

2) dp로 접근하자.
: 가방문제처럼 접근하면된다.

소스코드

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

int main()
{
	int n;
	cin >> n;
	
	vector<int>v(n);

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

	int m;
	cin >> m;

	//m을 v컨테이너를 통해 만들 수 있는 동전의 최소개수는?
	vector<int>dp(m + 1, INT_MAX);

	dp[0] = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = v[i]; j <= m; j++)
		{
			dp[j] = min(dp[j], dp[j - v[i]] + 1);
		}
	}

	cout << dp[m];
}