메모리

시간

1116 KB

4 ms

Code

#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
	int n,k;
	//가격을 만들 동전 갯수
	scanf("%d", &n);
	//동전 가치
	scanf("%d", &k);
	int coin;
	int	val[k + 1];
	int i = 1;
	//배열 초기화 10001은 경우의 수 없는 값
	while (i <= k)
		val[i++] = 10001;
	val[0] = 0;

	for (int j = 0; j < n; j++)
	{
		scanf("%d", &coin);
		for (int i = coin; i < k + 1; i++)
		{
			if (val[i - coin] != 10001)
				val[i] = min(val[i], (val[i - coin] + 1));
		}
	}
    if (val[k] == 10001)
        printf("%d",-1);
	else 
        printf("%d",val[k]);
	return 0;
}