백준(BOJ) 2294 동전 2 **

어렵지 않은 DP 문제

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <list>
#include <utility>
#include <functional>
#define maxi 10005

using namespace std;

int n,m,c[105],dp[10005];

int main(void)
{
	fill_n(&dp[0], maxi, maxi);
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%d", &c[i]);
	dp[0] = 0;
	for (int i = 0; i <= m; i++)
	{
		if (dp[i] != maxi)
		{
			for (int k = 0; k < n; k++)
			{
				if (i + c[k] <= maxi && dp[i + c[k]] > dp[i] + 1)
					dp[i + c[k]] = dp[i] + 1;
			}
		}
	}
	if (dp[m] == maxi)
		printf("-1");
	else
		printf("%d", dp[m]);
	return 0;
}