CodeIQ：3進法だとどう変わる？

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「3進法だとどう変わる？」（CodeIQ）を参照してください。

問題の概要

3進法には次の2とおりの表現方法があります。

【0,1,2を使う方法】
例）19(10進数) = 2 × 32 + 0 × 31 + 1 × 30 = 201(3進数)

【-1,0,1を使う方法】
例）19(10進数) = 1 × 33 + (-1) × 32 + 0 × 31 + 1 × 30 = 1T01(3進数)　※-1をTで表現しています。

標準入力から整数 n が与えられたとき、10進数で0以上 n 以下の数のうち、いずれの3進法での表現を使ってもすべての桁が同じになるような数がいくつあるかを標準出力に出力してください。

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def makeTritOff2(n, k=1, memo = [0,1])
	add_lst = []

	a = 3**k
	for i in memo
		m = a + i
		if m <= n then	add_lst.push(m)
		else break
		end
	end

	memo = memo + add_lst
	if m > n then	return memo
	else return makeTritOff2(n, k+1, memo)
	end
end

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

	puts makeTritOff2(line.to_i).length
end

解説

★★★の問題ですがわりとわかりやすいと思います。

考え方

2つの表記で同じになる値は「0,1,2」で2を使わないパターンと同じです。なので、このような値だけを選べばよいということになります。
私はメモ化再帰を使用して値を生成しました。

makeTritOff2()

3進数で2を使わない値を小さい方から入力値nまで作っています。
この関数の引数は、
　n: 入力値
　k: 3^kのk
　memo: 今まで作成した値のメモ
です。

[0,1]を初期値として3^kを足します。k=1の時は新たに[3,4]ができます。これは3進数で10と11です。k=2の時は[0,1,3,4]に9を足すので新たに[9,10,12,13]ができます。これは3進数で100、101、110、111です。
これを繰り返すことで無駄なく値を作成することができます。

雑感

「0,1,2」で2を使わない値が「-1,0,1」で-1を使わない値と同じパターンになることに気づいた時点でほとんど悩むことなくできました。ループを使った動的計画法でなく、メモ化再帰のコードを先に思いついたのは私にとってちょっと珍しかったと思います。