31問目
一度カウントに入れた通貨以下もののしか使用しないように注意して再帰呼び出しで終了。
一度1ペンスが使われたら1通りしかないため、1を返すようにした。
結果
73682
real 0m0.232s
user 0m0.221s
sys 0m0.010s
若干かかり過ぎなきはす。
pen = [200,100,50,20,10,5,2,1]
def get_pens(max, use=200):
if use == 1:
return 1
count = 0
for i in pen:
if i > max or i > use:
continue
elif i == max:
count +=1
else:
if i == use:
count += get_pens(max-i,use)
else:
count += get_pens(max-i,i)
#print "get_pens max:%d use:%d ,count:%d" % (max,use,count)
return count
if __name__ == '__main__':
print get_pens(200)