回分類題庫
b028: 忙碌的超商店員
關鍵字: 動態規劃-最少零錢數

測資點 : 5 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 1122 Times / 914 Users | Submit : 2159 Times / 992 Users | Accepted rate : 92%
題目加入時間 : 2011-10-20 13:11

Content: 简体中文

還記得有這樣的經驗嗎?你去買一個10元的東西,你付了1張100元的鈔票,店員卻找你9個10元,甚至有找你5個10元4個5元和10個1元的情況。為了避免這樣的情況,某超市在每一間門市都準備了足夠的零錢,並且要求店員找給顧客的零錢個數一定要是最少的。已知這個國家使用的貨幣有1元、5元、10元、12元、16元、20元等6種硬幣,你能幫他解決這個問題嗎?

Input:

輸入一個正整數 N (1<=N<=100),代表要找的錢。

Output:

請輸出找給顧客 N 元時,最少的零錢個數。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
輸入1:
13

輸入2:
29

Sample Output :

輸出1:
2

輸出2:
3

Hint :

Author :

動態規劃-最少零錢數 (管理員:sagit)

  Solve it!   Status Forum