Python(アルゴリズム)

今回はPythonを使用した全探索の処理を勉強したので共有したいと思います。

問題

10000円札と、5000円札と、1000円札が合計でN枚あって合計金額がY円となりました。

その場合の枚数を求めてください。
条件を満たさない場合は-1,-1,-1と出力します。

入力例
9 45000

出力例
4 0 5

下記がコードになります。

def Sample4():
    """
    お金の枚数を計算する。
    """
    N, Y = map(int, input().split()) # 入力する。Nが枚数Yが金額
    a, b, c = -1, -1, -1
    # 全探索
    for i in range(N + 1):
        for j in range(N + 1):
            n = N - i - j
            if n < 0 or n > N: # nが0以上N以下でない場合はスキップ
                continue
            if 10000 * i + 5000 * j + 1000 * n == Y: # 条件を満たすのか確認する。
                a, b, c = i, j, n
    print(f'1万円札{a}枚5千円札{b}枚千円札{c}枚')
Sample4()

以上になります。