문제 1404 숏다리의 계단오르기 챤스
[만든사람 : ]
문제 설명
n개의 계단이 있다. 영일이는 계단을 한 번에 1 칸 또는 2 칸 또는 3 칸을 오를 수 있다. 하지만, 한번에 3 칸을 오를 수 있는 챤스는 제한되어 있다.
계단의 수 n과 3칸을 오를 수 있는 제한된 횟수 m이 입력되면 영일이가 이 방법으로 계단을 올라갈 수 있는 서로 다른 방법의 수를 계산하는 프로그램을 작성하시오.
계단의 수 n과 3칸을 오를 수 있는 제한된 횟수 m이 입력되면 영일이가 이 방법으로 계단을 올라갈 수 있는 서로 다른 방법의 수를 계산하는 프로그램을 작성하시오.
입력 설명
계단의 수 n과 3칸을 오르는 제한된 횟수 m이 공백으로 구분되어 입력된다.
(1 <= n <= 20, 0 <= m <= 10)
(1 <= n <= 20, 0 <= m <= 10)
출력 설명
이 방법으로 계단을 올라갈 수 있는 서로 다른 방법의 수
입력 예시 복사
4 1
출력 예시 복사
7
도움
4개의 계단을 올라가는 방법 중에서 3계단 올라가기를 한 번 이내로 하는 경우의 수는 다음과 같이 총 7가지이다.
1 1 1 1
1 1 2
1 2 1
2 1 1
2 2
1 3
3 1
[힌트]
함수 f(k, x)는 k번째 계단에 위치하고 있으며, 이전까지 3계단 오르기를 총 x번 한 상태를 나타내는 함수이다.
*단, for, while과 같은 반복문을 사용해서는 안된다. goto 도 사용해서는 안된다.
1 1 1 1
1 1 2
1 2 1
2 1 1
2 2
1 3
3 1
[힌트]
함수 f(k, x)는 k번째 계단에 위치하고 있으며, 이전까지 3계단 오르기를 총 x번 한 상태를 나타내는 함수이다.
*단, for, while과 같은 반복문을 사용해서는 안된다. goto 도 사용해서는 안된다.