tags: APCS

Coin

題目解析

這個問題要求用最少數量的硬幣來湊出一個特定的金額，使用貪心算法是解決這類問題的有效方法。貪心算法的核心思想是每次選擇當前最大的硬幣，這樣可以最大化減少所需的硬幣數量。

解題方向

• 貪心算法：
  • 每次選擇能夠使用的最大面額的硬幣。
  • 用該硬幣盡可能地湊出所需的金額，然後對剩餘的金額繼續使用貪心策略。
• 步驟
  • 從最大面額的硬幣開始，計算需要多少枚該面額的硬幣來湊出金額的一部分。
  • 計算完後更新剩餘金額，繼續用剩餘的金額去使用下一個面額的硬幣。
  • 依次重複直到所有金額都換算成硬幣。

範例說明

假設硬幣面額為 [1, 5, 10, 50]，而需要換算的金額是 73 元：

• 先用 50 元的硬幣，可以湊出 1 枚（剩下 23 元）。
• 然後用 10 元的硬幣，可以湊出 2 枚（剩下 3 元）。
• 接下來用 1 元的硬幣，可以湊出 3 枚。
  總共使用了 1 + 2 + 3 = 6 枚硬幣，這就是最少的硬幣數量。

完整程式碼

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)
# 輸出最少需要的硬幣數量