[상태 정의를 통한 탐색] 계단 오르기 12

문제

OO이가 $n$칸 계단을 올라간다. 한 번에 1칸, 2칸, 3칸.

출발점은 0번째 또는 2번째. 또한 2번 연속 같은 칸 수만큼은 오르지 않는다.

$n$번째 칸까지의 방법의 수를 구하라.

$n=4$이면 0번 출발 3가지(1 2 1, 1 3, 3 1) + 2번 출발 1가지(2) = 4가지.