//有1，2，5三種硬幣
#include <iostream> 
#include <vector> 
using namespace std; 

int  change_money(vector<int> &ivec, int n) 
{ 
	ivec.push_back(0) ; //0分錢就不需要找 
    ivec.push_back(1) ; //1分錢只需要1個硬幣 
    ivec.push_back(1) ; //2分錢只需要1個硬幣 
    ivec.push_back(2) ; //3分錢需要2個硬幣 
    ivec.push_back(2) ; //4分錢需要2個硬幣 
    ivec.push_back(1) ; //5分錢需要1個硬幣 
    for(int i=6;i<=n;++i) 
	{ 
		int tmp1 = 1+ivec[i-1] ; 
        int tmp2 = 1+ivec[i-2] ; 
        int tmp5 = 1+ivec[i-5] ; 
        int tmp = tmp1 < tmp2 ? tmp1:tmp2; 
        tmp = tmp<tmp5 ? tmp:tmp5; 
        ivec.push_back(tmp); 
	} 
    return  ivec[i-1]; 
} 

int main() 
{ 
   cout << "請輸入要找的零錢數: " ; 
   int n; 
   cin >> n; 
   vector<int> ivec; 
   cout << "最少需要的硬幣數為:" << change_money(ivec,n); 
   cout << endl; 
   return 1 ;
}