7105 : 경우의 수 — 계단

시간 2.000s · 메모리 256MB · 제출 0 · 정답 0

코드제출 문제 풀기

채점기록 통계 묻고답하기

계단 n칸을 오르려고 합니다. 한 걸음에 최소 1칸에서 최대 K칸까지 오를 수 있습니다.
계단을 끝까지 오르는 서로 다른 방법의 수를 구하는 프로그램을 작성하십시오.

첫째 줄에 $n$과 $K$가 공백으로 구분되어 주어집니다. ($1 \le n \le 100, 1 \le K \le 10$)

경우의 수를 $10^9+7$로 나눈 나머지를 출력합니다.

4 2

점화식 dp[i] = Σ dp[i - j] (1 ≤ j ≤ K)를 이용하는 DP 문제이며 피보나치 수열의 확장형입니다.

조합론