연속 같은 보폭 금지

문제

명재현은 $n$칸짜리 계단의 0번째 칸에서 출발해 한 번에 1칸, 2칸, 3칸 중 하나를 오른다. 단, 1, 1이나 2, 2처럼 같은 칸 수로 연속해서 오르지 않는다. $n$번째 칸에 정확히 도착하는 방법의 수를 출력한다. 오르는 순서가 다르면 다른 방법으로 센다.

$n = 4$이면 1, 2, 1, 1, 3, 3, 1의 세 가지이다.