오르내리는 계단

문제

계단은 0번째 칸부터 $n$번째 칸까지 있고, 수빈은 0번째 칸에서 출발한다. 한 번에 2칸 또는 3칸을 오르거나, 1칸 또는 2칸을 내려갈 수 있다. 한 번 밟은 칸은 다시 밟지 않는다. 0번째 칸보다 아래나 $n$번째 칸보다 위로는 갈 수 없다.

이 조건을 지키며 $n$번째 칸에 도착하는 서로 다른 경우의 수를 구한다. $n$번째 칸에 도착하면 그 경로는 끝난다. $n = 4$이면 0 → 2 → 4, 0 → 2 → 1 → 4, 0 → 3 → 2 → 4, 0 → 3 → 2 → 1 → 4, 0 → 3 → 1 → 4의 5가지이다.