見出し画像
Photo by peishum

第5話 コインズ

Ghost

はじめに

　こちらでは，競技プログラミングコンテストサイトAtCoderの常設コンテスト「AtCoder Beginners Selection」に筆者が挑戦します．記事には，筆者が作成したコード(使用言語はPython)と簡単な解説を載せますので，プログラミング初心者の方の参考になれば幸いです．なお，この記事では，Pythonの詳細な文法については解説致しませんので，そちらに関しては関連記事および文献等を参照して頂きたく存じます．

問題(ABC087B - Coins)

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

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

コード(解答例)

A = int(input())
B = int(input())
C = int(input())
X = int(input())

count = 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:
                count += 1

print(count)

解説

　アーキテクチャとして良くないと思いますが，for文で総当たりしました．インターネットで他の解法がないか，調べてみたのですが，見当たりませんでしたね．初見では，動的計画法を用いるのかな，と思ったのですが上手くいきませんでした．もっとエレガントな方法を思いついた方がいらっしゃいましたら，ぜひコメントで教えてください！

いいなと思ったら応援しよう！