No.44 DPなすごろく
yuki2006問題文最終更新日: 2018-03-16 11:31:36
問題文
あなたは、Nマスのすごろくをしている。
毎ターン「１」または「２」前に進むことができる。
あなたは最初「０」のマスのスタートにいる。
ちょうどNマスに行く方法は何パターンありますか？
入力
N
すごろくのマス 整数\( N (2 \le N \le 50) \) が与えられます。
出力
ちょうどNマスにいく行く方法のパターン数を求めてください。
答えは\(2^{32} \) に収まらない時があるので注意してください。
64ビット整数型では収まります。
サンプル
サンプル1
入力
2
出力
2
2に行く方法は「1・1」と「２」の2パターンです。
サンプル2
入力
3
出力
3
3に行く方法は「1・1・1」と「２・１」と「１・２」の3パターンです。
「２・１」と「１・２」は区別するのでご注意ください。
サンプル3
入力
5
出力
8
「１・１・１・１・１」
「２・１・１・１」
「１・２・１・１」
「１・１・２・１」
「１・１・１・２」
「１・２・２」
「２・１・２」
「２・２・１」
の８通り
サンプル4
入力
50
出力
20365011074
答えは\(2^{32} \) を超えるのでintでは収まりません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。