ZeroJudge 解題筆記：d119. 有獎徵答：換零錢

作者：王一哲
日期：2025年8月23日


ZeroJudge 題目連結：d119. 有獎徵答：換零錢

解題想法

這題考動態規畫，使用的硬幣及鈔票面額有 (1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000)，先計算總金額為 0 ~ 50000 元所有的硬幣及鈔票面額組合數，再依照讀到的測資總金額查表、輸出答案。

Python 程式碼

使用時間約為 0.3 s，記憶體約為 5.6 MB，通過測試。

dp = [0]*(50001)  # 0 ~ 50000 各種金額組合數
dp[0] = 1  # 沒有用任何硬幣，1 種組合數
coins = (1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000)  # 可用的面額，要由小到大排序

for coin in coins:  # 依序讀取各種面額
    for j in range(coin, 50001):  # 依序更新 dp[coin] ~ dp[50000]
        dp[j] += dp[j - coin]  # dp[j] 的方法數要加上 dp[j - coin]

while True:
    arr = list(map(int, input().split()))  # 讀取一行資料
    if len(arr) == 1 and arr[0] == 0: break  # 如果 arr 長度為 1 而且等於 0，中止迴圈
    print(dp[sum(arr)] - 1)  # 查表找答案，要扣掉題目給的 1 種組合

C++ 程式碼

使用時間約為 21 ms，記憶體約為 1.5 MB，通過測試。

#include <iostream>
#include <sstream>
#define MAXN 50001
typedef long long LL;
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int coins[10] = {1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000};  // 可用的面額，要由小到大
    LL dp[MAXN] = {0};  // 0 ~ 50000 各種金額組合數
    dp[0] = 1;  // 沒有用任何硬幣，1 種組合數
    for(int i=0; i<10; i++) {  // 依序讀取各種面額，依序更新 dp[coin] ~ dp[50000]
        for(int j=coins[i]; j<MAXN; j++) dp[j] += dp[j - coins[i]];
    }
    string s;  // 暫存資料用的字串
    stringstream ss;  // 暫存分割後資料的容器
    while(getline(cin, s)) {  // 一次讀取一行
        if (s.size() == 1 && s == "0") break;  // 如果 s 只有一個 0，中止迴圈
        ss.clear(); ss << s;  // 清除 ss 再存入資料
        LL isum = 0;  // 加總
        while(ss >> s) isum += stoll(s);  // 輸出 ss 的資料存入 s ，s 轉成 LL 加到 isum
        cout << dp[isum]-1 << "\n";  // 查表
    }
    return 0;
}