합분해
DP[K][N]
초기화
DP[K][0]=1 => 0을 0으로 표현, 자리수 관계없이 -> 1가지 ex) 0,0,0 K=3,N=0
K=1 DP[1][N]=1 => ex) 5를 1자리에 표현
K=2 DP[2][N]=N+1
=> ex) 5를 하나씩 옆자리로 옮기면서 표현
5,0
4,1
3,2
2,3
1,2
0,5
0~5까지 세는 것과 동일
DP[3][1] = DP[2][0] + DP[2][1]
DP[3][2] = DP[2][0] + DP[2][1] + DP[2][2]
DP[3][3] = DP[2][0] + DP[2][1] + DP[2][2] + DP[2][3]
...
ex1)
DP[3][1] = DP[2][0] + DP[2][1]
0,1,0
0,0,1 => DP[2][1] : 0을 고정하면, K=2일때 1을 표현하는 방법
1,0,0 => DP[2][0] : 1을 고정하면, K=2일때 0을 표현하는 방법
ex2)
DP[3][2] = DP[2][0] + DP[2][1] + DP[2][2]
2,0,0 => DP[2][0] : 2를 고정하면, K=2일때 0을 표현하는 방법
1,1,0 => DP[2][1] : 1을 고정하면, K=2일때 1을 표현하는 방법
0,1,1
0,2,0
0,0,2 => DP[2][2] : 0을 고정하면, K=2일때 2를 표현하는 방법
점화식 도출
DP[K][N] = DP[K-1][N] + DP[K-1][N-1] + DP[K-1][N-2] + …. + DP[K-1][1] + DP[K-1][0]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static long[][] dp;
static long MOD = 1000000000L;
public static void main(String[] args) throws IOException {
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());
dp = new long[205][205];
for (int i = 0; i <= K; ++i)
dp[i][0] = 1;
for (int i = 0; i <= N; ++i) {
dp[1][i] = 1;
dp[2][i] = i + 1;
}
for (int i = 3; i <= K; ++i) {
for (int j = 1; j <= N; ++j) {
for (int k = 0; k <= j; ++k) {
dp[i][j] += dp[i - 1][k]%MOD;
}
}
}
System.out.println(dp[K][N]%MOD);
}
}
