go言語を始めてみた その２ codeIQの問題に挑戦

codeIQの3233に挑戦しました

ダイアルを回す回数と総メモリ数から回し方が何パターンあるのか求める問題です。

タイトル通りgoで回答を書いて提出。
結果は処理時間オーバーでした。。

再帰を使っているので回す回数が大きくなってくると厳しいですね

やってて少しつまったところとしては、
標準入力のsplitですね

reader := bufio.NewReader(os.Stdin)
input, _ := reader.ReadString('\n')
inputList := strings.Split(input, " ")
times, _ := strconv.Atoi(inputList[0])
length, _ := strconv.Atoi(inputList[1])

こう書いていたら何故か２番目の数字が取得できず。。
どうやらinput変数の末尾に改行文字が入っているのが原因のようです
splitの前に

input = strings.TrimRight(input, "\n")

を入れたら取得できるようになりました。

あとは計算量を減らせばいけるはずなのですが、どう減らせばいいのか。。