【python】合計金額に対する紙幣＆貨幣の必要最小枚数を算出する

■概要

いくつかの合計金額に対して、紙幣または貨幣の必要最小枚数を算出する処理を実装する。

例：
合計金額が1,230円の場合
1,000円札：1枚、100玉：2枚、10円玉：3枚

なお、実装するにあたり、前提条件を以下に示す。

• 使用する紙幣＆貨幣は、1万円、5,000円, 1,000円, 500円, 100円, 50円, 10円, 5円, 1円
  ※2,000円は使用しない
• 合計金額がマイナスまたは0（ゼロ）の場合は、使用する紙幣＆貨幣をゼロとする

■フローチャート

実装する処理のフローチャートを以下に示す。

・メイン処理

・最小枚数算出処理

■サンプルコード

# 紙幣＆貨幣リスト
MONEY_LIST = [10000, 5000, 1000, 500, 100, 50, 10, 5, 1]

# 試験用合計金額リスト
TOTAL_MONEY_LIST = [
    73735, 9561, 4950, 600, 70590,
    117440, 2350, 0, 52318, 12524,
    55220, 510546, -6632, 523871
    ]


# 最小枚数を計算する処理
def cal_minimum_number(total_money):
    # 返却用辞書型
    dict_result = {}

    # 紙幣＆貨幣リスト分繰り返し
    for money in MONEY_LIST:
        # 紙幣＆貨幣カウンタの初期値セット
        count = 0

        # 合計金額が紙幣、貨幣以上の場合繰り返し
        while total_money >= money:
            # 合計金額を減算
            total_money -= money
            # カウンタインクリメント
            count += 1

        # 結果を返却用辞書型にセット
        dict_result[money] = count

    # 結果を返す
    return dict_result


# メイン処理
if __name__ == '__main__':
    # 試験用合計金額リスト分繰り返し
    for total_money in TOTAL_MONEY_LIST:
        # 最小枚数の結果を取得
        result = cal_minimum_number(total_money)

        # 最小枚数の結果を表示
        print(total_money, result)

■実行結果

73735 {10000: 7, 5000: 0, 1000: 3, 500: 1, 100: 2, 50: 0, 10: 3, 5: 1, 1: 0}
9561 {10000: 0, 5000: 1, 1000: 4, 500: 1, 100: 0, 50: 1, 10: 1, 5: 0, 1: 1}
4950 {10000: 0, 5000: 0, 1000: 4, 500: 1, 100: 4, 50: 1, 10: 0, 5: 0, 1: 0}
600 {10000: 0, 5000: 0, 1000: 0, 500: 1, 100: 1, 50: 0, 10: 0, 5: 0, 1: 0}
70590 {10000: 7, 5000: 0, 1000: 0, 500: 1, 100: 0, 50: 1, 10: 4, 5: 0, 1: 0}
117440 {10000: 11, 5000: 1, 1000: 2, 500: 0, 100: 4, 50: 0, 10: 4, 5: 0, 1: 0}
2350 {10000: 0, 5000: 0, 1000: 2, 500: 0, 100: 3, 50: 1, 10: 0, 5: 0, 1: 0}
0 {10000: 0, 5000: 0, 1000: 0, 500: 0, 100: 0, 50: 0, 10: 0, 5: 0, 1: 0}
52318 {10000: 5, 5000: 0, 1000: 2, 500: 0, 100: 3, 50: 0, 10: 1, 5: 1, 1: 3}
12524 {10000: 1, 5000: 0, 1000: 2, 500: 1, 100: 0, 50: 0, 10: 2, 5: 0, 1: 4}
55220 {10000: 5, 5000: 1, 1000: 0, 500: 0, 100: 2, 50: 0, 10: 2, 5: 0, 1: 0}
510546 {10000: 51, 5000: 0, 1000: 0, 500: 1, 100: 0, 50: 0, 10: 4, 5: 1, 1: 1}
-6632 {10000: 0, 5000: 0, 1000: 0, 500: 0, 100: 0, 50: 0, 10: 0, 5: 0, 1: 0}
523871 {10000: 52, 5000: 0, 1000: 3, 500: 1, 100: 3, 50: 1, 10: 2, 5: 0, 1: 1}