---
# System prepended metadata

title: Coin
tags: [APCS]

---

###### tags: `APCS`
# **Coin**
### **題目解析** 
這個問題要求用最少數量的硬幣來湊出一個特定的金額，使用貪心算法是解決這類問題的有效方法。貪心算法的核心思想是每次選擇當前最大的硬幣，這樣可以最大化減少所需的硬幣數量。
### **解題方向** 
* 貪心算法：
    * 每次選擇能夠使用的最大面額的硬幣。
    * 用該硬幣盡可能地湊出所需的金額，然後對剩餘的金額繼續使用貪心策略。
* 步驟
    * 從最大面額的硬幣開始，計算需要多少枚該面額的硬幣來湊出金額的一部分。
    * 計算完後更新剩餘金額，繼續用剩餘的金額去使用下一個面額的硬幣。
    * 依次重複直到所有金額都換算成硬幣。
### **範例說明**
假設硬幣面額為 [1, 5, 10, 50]，而需要換算的金額是 73 元：
* 先用 50 元的硬幣，可以湊出 1 枚（剩下 23 元）。
* 然後用 10 元的硬幣，可以湊出 2 枚（剩下 3 元）。
* 接下來用 1 元的硬幣，可以湊出 3 枚。
總共使用了 1 + 2 + 3 = 6 枚硬幣，這就是最少的硬幣數量。
### **完整程式碼**
```python=
coins = list(map(int, input().split()))
# 輸入硬幣的面額種類，並轉換成整數列表

money = int(input())
# 輸入要換算的金額

num = 0
# 初始化硬幣數量計數器

# 從最大的面額開始計算硬幣數量
for i in range(len(coins) - 1, -1, -1):
    num = num + money // coins[i]
    # 計算當前面額的硬幣可以湊出的數量
    money = money % coins[i]
    # 更新剩餘金額為餘數部分

print(num)
# 輸出最少需要的硬幣數量
```