계단 오르기 (L) [1132 / 046C]
Time Limit(Test case) : 1000(ms)Number of users who solved : 292 Total Tried : 2741
The Champion of this Problem (C++) : gs16109 - ms / 161byte
My Best Submission (C++) : N/A
[JeongHJ]
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<= 1,000,000
Output
경곽이가 계단을 오를 수 있는 모든 경우의 수를 출력한다. 단, 수가 너무 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.IO Example
입력7 5
출력
18
Prob Analysis : [Problem Statistics] | [Solution]
