#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;
}

 

주석좀 달아주세요

동전교환문제

이 게시물을...