いまだに現金払い？：「プログラマ脳を鍛える数学パズル」Q05の答え

問題

最近は電車もバスも電子マネーが当たり前。
でも、いまだに現金で払う人も意外と多いもの。

今回はバスに設置されている両替機を考えます。
この機械では、10円玉、50円玉、100円玉、500円玉の組み合わせに両替することができ、いずれの硬貨も十分な枚数がセットされています。
（バスの運賃は現金の場合は10円単位になっているため、1円玉、5円玉は取り扱っていません）

両替する際に、使われない硬貨はあっても構いませんが、バスの中でたくさんの小銭が出ると困るため、最大で15枚になるように両替します。
例えば、10円玉を100枚、という両替はできません。

このとき、1000円札を入れたときに出てくる硬貨の組み合わせは何通りあるかを求めてください。
なお、硬貨の順番は区別しないものとします。

元ネタ：
第40回「今週のアルゴリズム：いまだに現金払い？」正解者発表｜CodeIQ MAGAZINE

わたしの考え方

総当たり式でループを作り、合計額が1000円かつ合計枚数が15枚以下の組み合わせを抽出する。
500円玉は0枚から2枚、100円玉なら0枚から10枚までとループの数は調整できる。

わたしのオリジナル解答

#coding: UTF-8
a = 0
for m in range (0, 3): #500円玉は0から2枚
    for n in range (0, 11): #100円玉は0から10枚
        for o in range (0, 16): #50円玉は0から15枚
            for p in range (0, 16): #10円玉は0から15枚
                if 500 * m + 100 * n + 50 * o + 10 * p == 1000 and m + n + o + p < 16:
                    a += 1
                    print [m, n, o, p]
print a

模範解答のミソ

模範解答もまずはわたしの答えと同じく単純なループで解いている。
拡張性を意識した別解答では、Rubyのrepeated_combinationメソッドを用いて、組み合わせを吐き出している。

修正されたわたしの解答

import itertools

a = 0
coins = [10, 50, 100, 500]
for n in range (2, 16):
    for combi in itertools.combinations_with_replacement(coins, n):
        if sum(combi) == 1000:
            print combi
            a += 1
print a