CodeIQ：【実力判定：Aランク】小銭王子

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「【実力判定：Aランク】小銭王子」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

【問題】
小銭をたくさん持っている小銭王子は、小銭を使った支払いに興味を持ちました。
指定された金額になる小銭の出し方のすべてのパターンを調べ、王子に教えてあげてください。
例えば、10円を支払うとき、「10円玉1枚」「5円玉2枚」「5円玉1枚と1円玉5枚」「1円玉10枚」の4通りあります。
※小銭は500円・100円・50円・10円・5円・1円硬貨です。また、小銭王子はそれぞれの硬貨を1000枚ずつ持っています。

【入力】
標準入力から、整数値N（1≦N≦1000）が与えられます。

【出力】
合計金額がN円になる硬貨の出し方のすべての組み合わせを求め、そのパターン数を、標準出力に出力してください。

【入出力サンプル】
Input

10
標準出力

4

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

Coin = [500,100,50,10,5,1]
$Cnt = 0

def solve(n, c)
	if Coin[c] == 1 then
		$Cnt += 1
		return
	end

	for i in 0..n/Coin[c]
		amari = n - (i*Coin[c])
		if amari == 0 then
			$Cnt += 1
		else
			solve(amari, c+1)
		end
	end
end

# main
while line = gets
	line.strip!
	if line.empty? then next end

	solve(line.to_i, 0)
	p $Cnt
end

解説

Aランクの問題です。
Bランクに比べると格段に難しくなっています。

考え方

コードは再帰で見通しが悪いので具体的な値を例にしてみます。
例の10円の場合で考えてみましょう。面倒なので10円、5円、1円だけしかないとして考えます。

額の大きい硬貨から数を確定し、あまりを小さい硬貨に回すということを繰り返せばパターンを列挙できます。
10円を1枚使った場合、あまりは0なので5円は0枚、さらにあまりは0なので1円は0枚です。
10円を0枚使ったらあまりは10なので5円は0〜2枚使えます。
10円を0枚、5円を2枚使ったらあまりは0なので1円は0枚です。
10円を0枚、5円を1枚使ったらあまりは5なので1円は5枚です。
10円を0枚、5円を0枚使ったらあまりは10なので1円は10枚です。
これで例の通り4パターン列挙できました。

このように大きい硬貨を0〜最大数まで使用し、その額を引いた余りを一つ小さい額の硬貨に適用するという処理を再帰的に繰り返せばパターンを列挙できます。

solve()

引数nは金額、cは定数Coinのインデックス番号です。
定数コインは硬貨を額面の大きいものから並べた配列です。
大域変数$Cntはパターン数です。

7〜10行目の処理は使用する硬貨が1円の場合の処理です。1円を使う場合、n枚の1円を使うしかないので1〜nまでのパターンを試す必要がありません。また、1円を処理する時点でパターンが確定しますので$Cntを1増やします。

12行目〜19行目のループはcに渡ってきた硬貨を使える枚数までのパターンを列挙し、各パターンに対して金額にあまりがあれば硬貨の額面を1段階小さくして余りと次の硬貨を指定して同様の処理を繰り返すという処理をします。
n=10の場合を例に説明します。
最初の呼び出しではc=0(Coin[0]=500)なのでn/Coin[c]=0となり500円は0枚だけを処理します。
2回目の呼び出しではn=10、c=1(Coin[1]=100)なのでn/Coin[c]=0となり500円は0枚だけを処理します。
3回目の呼び出しではn=10、c=2(Coin[2]=50)なのでn/Coin[c]=0となり50円は0枚だけを処理します。
4回目の呼び出しではn=10、c=3(Coin[3]=10)なのでn/Coin[c]=1となり10円は0〜1枚を処理します。
5回目の呼び出しは4回目でi=0の場合なのでn=10、c=4(Coin[4]=5)なのでn/Coin[c]=2となり5円は0〜2枚を処理します。
6回目の呼び出しは5回目でi=0の場合なのでn=10、c=5(Coin[5]=1)なので1つ目のパターン（全部1円）が確定します。
7回目の呼び出しは5回目でi=1の場合なのでn=5、c=5(Coin[5]=1)なので2つ目のパターン（5円1枚、1円5枚）が確定します。
5回目のi=2の場合、余りは0なので3つ目のパターン（5円2枚）が確定します。
4回目のi=1の場合、余りは0なので4つ目のパターン（10円1枚）が確定します。

ちなみに13円の様に必ず1円を使わなければならない場合は7〜10行目の処理で吸収されるので気にしなくても大丈夫です。

雑感

いかにも再帰を使ってやりなさいという感じの問題です。しかし、メモ化などの工夫は要らないので出題者によっては★★程度の難易度です（この問題は★★★でした）。
Cランク、Bランクの差に比べるとBランクとAランクの差の方が大きいと思います。