문제 설명

처음에 문제를 이해하는데 매우 오랜시간이 걸림.
예시에서 왜 4 2 입력이 18출력인지를 이해못했다.

문제를 잘 읽자....
난 처음에 나보다 절댓값으로 K이하로 차이나는 수 뒤에만 올 수 있는 줄 알았다.
알고보니, 내 앞 수가 나보다 크면 상관없고 작다면 K 차이까지만 허용해준다는 의미였다.

이걸 알고 문제를 다시보니 풀이가 생각났다.
K는 어차피 문제마다 고정이므로 별도로 dp에 반영해서 저장하지 않아도 된다고 생각했고, 일단 일차원 테이블을 세웠다. dp[k]는 k까지의 수를 고려해서 일자로 규칙대로 세웠을 때의 경우의 수다.

다음과 같은 경우가 dp[4] 라고 생각하자. 이때 dp[5]는 몇 가지일까?
우선, 5를 새롭게 추가해야하는데, 5의 뒤에 올 수 있는 수는 1~4 모두가 가능하지만 5앞에 올 수 있는 수는 몇가지 일까? 바로 3,4 2가지밖에 안된다. K가 2이기 때문이다.
그렇다면, 우리는 dp[4]에서 구한 경우의 수들의 3과 4 뒤에 5를 세울 수 있다.
그리고 5는 모든 수 앞에 올 수 있으므로, dp[4]의 모든 경우의 수의 앞에 5만 추가해 준 경우도 생각할 수 있다.

그렇다면 점화식은 간단하다.

dp[n] = (K+1)dp[n-1] (단, K는 n-1보다 작은 경우)

하지만, 위 수식은 int형 범위를 벗어날 수 있다. 그러므로, 처음 계산은 long으로 받아주고, 모듈러 연산을 1000_000_007 로 할때, 다시 int로 형변환해서 dp에 저장하는 걸 잊지 말자.

문제 풀이

import java.io.*;
import java.util.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		if (N == 1 || N ==2) {
			System.out.println(N);
			return;
		}
		int[] dp = new int[N+1];
		dp[1] = 1;
		dp[2] = 2;
		for(int i=3; i<=N; i++) {
			int canFrontCount = Math.min(K, i-1);
			long next = (canFrontCount + 1)*(long)dp[i-1];
			dp[i] = (int)(next % 1000000007);
		}
		System.out.println(dp[N]);
	}
}