零錢問題

/**********************************************************************************/
/*  Problem: b028 "忙碌的超商店員" from 動態規劃-最少零錢數                                       */
/*  Language: C++                                                                 */
/*  Result: AC (3ms, 132KB) on ZeroJudge                                          */
/*  Author: jw910731 at 2018-07-25 14:00:13                                       */
/**********************************************************************************/

#include <cstdio>
using namespace std;
int dp[101] = {0},coin[6]={1,5,10,12,16,20};
void dp_gen(){
    for(int i=0;i<6;i++) dp[coin[i]] = 1;
    for(int i=1;i<=100;i++){
        int min = dp[i-1];
        for(int j=0;j<6;j++){
            if(i>=coin[j]){
                if(dp[i-coin[j]] < min){
                    min = dp[i-coin[j]];
                }
            }
        }
        dp[i] = min+1;
    }
}
int main(){
    dp_gen();
    int n;
    scanf("%d",&n);
    printf("%d\n",dp[n]);
    return 0;
}