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

문제

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

같은 칸 수만큼 오르는 일을 $k$번 이상 하지 않는다. 즉 각 step 타입을 최대 $k-1$번까지만 쓴다.

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

$n=5$, $k=3$이면 다음 8가지.

1 1 3
1 2 2
1 3 1
2 1 2
2 2 1
2 3
3 1 1
3 2

1 2 1 1은 1칸 이동을 3번 써서 제외.

제한

• $1 \le n \le 15$
• $1 \le k \le 15$

입출력 예시

입력 1 5 3 → 출력 1 8

입력 2 4 2 → 출력 2 2

출처

KOISTUDY [상태 정의를 통한 탐색] 시리즈.

제한

• $1\le n\le$