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

문제

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

OO이는 0번째 칸 또는 2번째 칸에서 출발할 수 있다.

$n$번째 칸까지의 방법의 수를 구하라 (두 출발점에서의 경우를 모두 합해서).

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

입출력 예시

입력 1 3 → 출력 1 4

입력 2 4 → 출력 2 7

제한

• $1 \le n \le 15$

출처

KOISTUDY [상태 정의를 통한 탐색] 시리즈에서 가져온 문제이다.