Informatica Online Judge

  계단 오르기 (S) [1131 / 046B]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 300   Total Tried : 452


The Champion of this Problem (C++) : gs14049 - 0ms / 111byte
My Best Submission (C++) : N/A

[koistudy.net (T. HJ Jeong)]

Background

경곽이는 오늘 계단을 오르는 꿈을 꾸었다. 꿈에 계단을 오르다가 그만 계단 밑으로 떨어지는 꿈이었다. 아침에 일어난 경곽이는 꿈에서 영감을 얻어 다음과 같은 계단 오르기 문제를 만들었다.

한 번에 1칸, 2칸 혹은 3칸을 오를 수 있다. 하지만 계단 중에는 계단이 파괴되어 밟을 수 없는 경우가 있다.

즉 경곽이가 계단을 8칸을 올라가야 하고 부서진 계단이 4번째 계단이라고 가정하자.1 1 1 2 1 1 1 이는 모두 1칸씩 이동하고 3번째 칸에서 5번째 칸으로 2칸을 이동하고 나머지는 1칸을 이동하여 8칸을 이동한 예이다.

그리고 3 2 2 1 도 가능하다.계단의 수 n과 파괴된 계단번호 k가 주어질 때, 경곽이가 계단을 올라갈 수 있는 서로 다른 방법의 수를 모두 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 n, k가 입력된다.

[입력값의 정의역]
1 <= n, k<= 30

Output

경곽이가 계단을 오를 수 있는 모든 경우의 수를 출력한다.

IO Example

입력
7 5

출력
18

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]