메모리
시간
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;
}
C++
복사