계단 오르기

문제

계단이 n개 있다. 한 번에 1칸 또는 2칸씩 오를 수 있을 때, n번째 계단에 도착하는 방법의 수를 구하라.

예: n = 3일 때 방법은 1+1+1, 1+2, 2+1 세 가지이다.

점화식: dp[i] = dp[i-1] + dp[i-2].

n이 최대 50이므로 결과가 32비트를 넘을 수 있다. long long으로 출력한다.

입출력 예시

입력 1