公平に分けられたケーキ（Ruby）

アルゴリズム・パズルです。

問題：
16cm × 12cm の長方形のケーキがあります。二人で交互にケーキを切るのですが、ケーキを切った人が小さい方のケーキを取り、交代して残りをさらに切るというようにします。（ただし切り方は、辺に平行に直線的に切り、しかも切ってできたケーキの辺の長さは cm 単位になるようにします。）これを最小が 1cm × 1cm になるまで続けます。
さて、切り終えたとき二人の取ったケーキのそれぞれの総量が等しくなるとします。このような切り方は何とおりもありますが、その中で切った「切り口」の長さの総和を出すとき、その最小値を求めなさい。

　
Ruby で解いてみました。コードは以下です。
q56.rb

require 'set'

#(x, y)のケーキを切ってできる全ての (面積, 切った長さの合計) のペアを返す
#ただし面積はここでカットした人の総計
def cut(x, y)
  x, y = y, x if x < y
  return @memo[[x, y]] if @memo.has_key?([x, y])
  return Set[[1, 1]] if x == 2 and y == 1
  
  result = Set.new
  
  #前の人がカットしたところから自分の分を求める
  calc = proc do |s, t|
    cut(s, t).each do |sqar, ln|
      square = x * y - sqar
      next if square > X * Y / 2    #高速化
      length = ln + s
      result << [square, length]
    end
  end
  
  #可能なあらゆる場合でケーキを切る
  (x / 2).times {|i| calc.call(y, x - i - 1)}
  (y / 2).times {|i| calc.call(x, y - i - 1)}
  
  @memo[[x, y]] = result
end

X, Y = 16, 12
@memo = {}

result = cut(X, Y)
p result.select {|sqar, _| sqar == X * Y / 2}.sort_by {|_, ln| ln}[0]    #=>[96, 47]

答えは 47cm です。これはかなりむずかしかったです。あまりいい解き方とも思えません。実行時間は自分の環境で 1.5秒ほどでした。もっとも深いループの回数は 1386985回です。

なお、標準添付ライブラリの set を使っていますが、これを配列でやると飛んでもないことになってしまいます。

※追記（3/7）
ハッシュを使ってほんの少し書き替えたところ、劇的に高速化しました。実行時間は 0.05秒ほどになりました。じつに 30倍の高速化です。アルゴリズムはまったく同じですが、探索の際にうまく枝刈りをする方法を思いつきました。もっとも深いループの回数は 33192回なので、ほぼ 1 / 40 になっています。コードはこちら。30cm × 30cm の場合でも 0.5秒足らずで終了します。
　
※再追記（4/14）
あとから見なおしたらよくこんなこと思いついたなと思いました。関数 calc で前の面積から次の面積を求めるところが我ながら巧妙かと感じます。
　