AtCoder ABC 087 B – Coins Python解説

2021年11月27日

Coins

あなたは、500 円玉を A 枚、100 円玉を B 枚、50 円玉を C 枚持っています。 これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りありますか。

同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

AtCoder Beginner Contest 087 「Coins」

A,B,Cの枚数は最大でも50枚なので、全探索でも50^3で済みます。
ということで、今回は愚直にfor文3重ループで計算していきます。

a = int(input())
b = int(input())
c = int(input())
x = int(input())

cnt = 0

for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if 500*i + 100*j + 50*k == x:
                cnt += 1

print(cnt)

今回は3重ループでも行けましたが、問題によっては計算量が多くなりすぎて制限時間に間に合わなくなる場合があります。

その際は3重ループを2重ループにするなどの工夫が必要です。