#include <stdio.h>
int coin_Kind[12] = {};
int memo[100002][12] = {};
int check1(int M,int n)
{
if(M == 0)
return 0;
if(memo[M][n] != 0)
return memo[M][n];
int min = 100000,a = 100000,c = 1,s=n;
n--;
while(1){
if(n < 0){
memo[M][s] = min;
return min;
}
if(M - coin_Kind[n] * c >= 0)
{
a = c + check1(M - coin_Kind[n] * c,n);
if(a < min)
min = a;
}
else
{
n--;
c = 0;
}
c++;
}
}
int coin(int M,int n)
{
for(int i = 0;i < n;i++){
scanf("%d",&coin_Kind[i]);
}
return check1(M,n);
}
int main()
{
int M,n;
scanf("%d %d",&M,&n);
printf("%d",coin(M,n));
return 0;
}
top of page
실제 작동 상태를 확인하려면 라이브 사이트로 이동하세요.
수정: 2월 28일
거스름돈 ||
거스름돈 ||
댓글 0개
좋아요
댓글(0)
bottom of page