アルゴリズムとデータ構造

階段

あなたは n 段の階段を登ろうとしています。各ステップで、一度に2段進むか、1段ずつ進むかを選択できます。このとき、階段を登る方法は全部で何通りあるでしょうか？

入力

入力として、整数 n（1 ≤ n ≤ 45）が1つ与えられます。

出力

出力には、階段を登る方法の総数を表示してください。

例

入力
出力
2
2
3
3

説明

  1. 2段の階段の場合 → (1) 1段 + 1段、(2) 2段
  1. 3段の階段の場合 → (1) 1段 + 1段 + 1段、(2) 1段 + 2段、(3) 2段 + 1段
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue