
#include <iostream>
#include <stdio.h>
using namespace std;
int C[1000001];
int d[1000];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int i,j,W,N;
scanf("%d",&N);
for(i=0;i<N;i++)
{
scanf("%d",&d[i]);
}
scanf("%d",&W);
for(i=1;i<=W;i++)
{
C[i]=9999;
}
for(i=0;i<N;i++) {
for(j=1;j<=W;j++) {
if(C[j]>C[j-d[i]]+1 && d[i]<=j) {
C[j]=C[j-d[i]]+1;
}
}
}
printf("%d",C[W]);
return 0;
}
주석좀 달아주세요
동전교환문제