クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「2-2 硬貨の問題」(p.42)

Pythonで理解する蟻本（プログラミングコンテストチャレンジブック）

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-2 硬貨の問題」(p.42)
のコードをPythonで書き直したものとなっています。

入力

C_{1}\,C_{5}\,C_{10}\,C_{50}\,C_{100}\,C_{500}\\A

入力例



3 2 1 3 0 2
620


解答

# コインの金額
V = [1, 5, 10, 50, 100, 500]

# 入力
C = list(map(int,input().split()))    # C[0] = C_1, C[1] = C_5, ...
A = int(input())

ans = 0

for i in range(5, -1, -1):
    t = min(A // V[i], C[i])    # コインiを使う枚数
    A -= t * V[i]
    ans += t

print(ans)