競技プログラミング

【超初心者向け】AtCoderで最初に解くべき過去問集を分かりやすく解説します【4問目】

プログラミング

こんにちは!サトシ(@satoshi365_blog)です!

 

この記事では、「AtCoderに登録して最初に解くべき10問(AtCoder Beginners Selection)」の4問目「Coins」をめちゃくちゃ分かりやすく解説していきます。

AtCoder で問題を解くためには、新規登録しないといけません。

新規登録はこちらから → AtCoder に新規登録する

 

それでは、「Coins」の解説をしていきます!

プログラミング
【競プロ】最初に解くべき過去問10問をPythonで分かりやすく解説します!【AtCoder】こんにちは!サトシ(@satoshi365_blog)です! この記事では、「競技プログラミング(AtCoder)に登録し...

4問目「Coins」で身につくスキル

この問題は、今までのスキルを応用するだけで解けます

 

なので、この問題で新しく身に付くスキルはありません。

 

4問目「Coins」の解説

この順番で解説していきます。

  • 問題文
  • 入力例と出力例
  • 解答例
  • 解説

それでは見ていきましょう。

 

問題文

 

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

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

制約
・0 ≤ A, B, C ≤ 50
・A + B + C ≥ 1
・50 ≤ X ≤ 20000
・A, B, C は整数である
・X は 50 の倍数である

入力
入力は以下の形式で標準入力から与えられる。

A
B
C
X

出力
硬貨を選ぶ方法の個数を出力せよ。

ABC087B – Coinsより引用

 

入力例と出力例

入力例

1
5
1
500

出力例

2

500 円玉 1 枚、100 円玉 5 枚、50 円玉 1 枚で 合計金額を 500 円にする方法は、2通りあります。

1つは、500 円玉1枚のとき、
もう一つは、100 円玉 5 枚のときです。

 

解答例

a, b, c, x = [int(input()) for _ in range(4)]
ans = 0
for i in range(a + 1):
  for j in range(b + 1):
    for k in range(c + 1):
      if i * 500 + j * 100 + k * 50 == x:
        ans += 1
print(ans)

解説

  1. 500円が0枚、100円が0枚、50円が0枚の時、X円になるか
  2. 500円が0枚、100円が0枚、50円が1枚の時、X円になるか
  3. 500円が0枚、100円が0枚、50円が2枚の時、X円になるか

と全パターンを計算してみて、X 円になる回数を数えます。

 

では、コードを詳しく解説していきます。

 

まずは、a, b, c, x を受け取ります。

a, b, c, x = [int(input()) for _ in range(4)]

 

硬貨を選ぶ方法が何通りあるか数えるために、ans を作っておきます。

ans = 0

 

下の部分で全パターンを調べています。

※range(5) とすると、i が 0〜4 までの for になることに注意してください。

for i in range(a + 1):
  for j in range(b + 1):
    for k in range(c + 1):

 

そして、合計 X 円になったときは、ans に1を足します。

    if i * 500 + j * 100 + k * 50 == x:
      ans += 1

 

そして、全パターンを調べ終わったら、ans を出力します。

print(ans)

 

まとめとして、もう一度プログラムを確認してみましょう。

a, b, c, x = [int(input()) for _ in range(4)]
ans = 0
for i in range(a + 1):
  for j in range(b + 1):
    for k in range(c + 1):
      if i * 500 + j * 100 + k * 50 == x:
        ans += 1
print(ans)

これで、「X 円になるように硬貨を選ぶ方法が何通りあるか」を求めることができました。

まとめ

もし分からない点などありましたら、気軽にTwitterなどでご質問ください^^

少しでも参考になれば嬉しいです!

COMMENT

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です