[C++] 백준 2294 동전2

#include <iostream>
#include <vector>
#include <queue>
 
int dp[10001] = {};
 
int main() 
{
	int n = 0;
	int k = 0;
	std::cin >> n >> k;
 
	int iMax = k;
 
	for (int i = 0; i <= 10000; ++i)
	{
		dp[i] = 10001;
	}
 
	std::vector<int> vec(n,0);
 
	for (int i = 0; i < n; ++i)
	{
		std::cin >> vec[i];
 
		if (vec[i] <= 10001)
			dp[vec[i]] = 1;
	}
 
	for (int i = 0; i <= k; ++i)
	{
		if (dp[i] != 10001)
		{
			for (int j = 0; j < vec.size(); ++j)
			{
				if (vec[j] <= 10001)
				{
					if (i + vec[j] <= 10000 && i + vec[j] <= k)
					{
						if (dp[i + vec[j]] > dp[i] + 1)
							dp[i + vec[j]] = dp[i] + 1;
					}
				}
			}
		}
	}
 
	if (dp[k] == 10001)
		std::cout << -1;
	else
		std::cout << dp[k];
 
	return 0;
}

이전 동전 문제랑 비슷하게 풀었다.

1. 받은 숫자들에다가 갯수 1 (최대 수인 10001이 넘어가면 패스)

2. 할 수 없는 숫자면 넘어가고 할 수 있다면 vec에 있는 만큼 돌려서 추가 숫자로 입력