切換
舊版
前往
大廳
主題

ZeroJudge - b511: 換銅板 解題心得

Not In My Back Yard | 2018-10-22 13:45:42 | 巴幣 100 | 人氣 466

題目連結:


題目大意:
給定一個正整數N(N ≦ 5),接下來有N個數字,代表N個硬幣面額。再來有一個數字P,表示要找零的金額(硬幣面額和金額都是不超過100的正整數)。

求所有找零的方法,格式詳見範例輸出。並以字典序由小到大輸出。



範例輸入:
3
1 5 10
17



範例輸出:
(2,1,1)
(2,3,0)
(7,0,1)
(7,2,0)
(12,1,0)
(17,0,0)

註:括號裡第一個數字代表第一個面額,第二數字代表第二個硬幣面額,以此類推。因此,面額輸入順序會影響答案。



解題思維:
窮舉第一種硬幣可能的數量,然後對每個可能遞迴到第二種硬幣可能的數量(記得減掉第一種硬幣的金額),以此類推。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作