Time Limit: 1s
Memory Limit: 128MB
웰시씨는 강의실에 가기 위해 n개의 계단을 올라야하는데, 다리가 짧아 슬픈 웰시씨는 계단을 오를 때 한 번에 많아야 2칸까지만 오를 수 있다.
식상한 것이 싫었던 웰시씨는 매일 새로운 방법으로 계단을 오르려고 한다.
과연 n개의 계단을 오르는 경우의 수는 총 몇 가지인지 계산해보자.
* Line 1: 계단의 갯수 n (1≤n≤20)
* Line 1: n개의 계단을 오르는 경우의 수를 출력한다.
4
5
계단 네 칸을 올라가는 방법은
1 1 1 1
1 1 2
1 2 1
2 1 1
2 2
총 다섯 가지다.
계단을 오르는 방법의 수 = 맨 마지막에 한 칸 올라가는 방법의 수 + 맨 마지막에 두 칸 올라가는 방법의 수