μ΄λ² λ¬Έμ λ νΌμ νμ΄μ λ§€μ° λΏλ―νλ λ¬Έμ !
ν¬κΈ°νμ§ μμμ κ²°κ΅ ν μ μμλ€~
DPλ¬Έμ λ Dpλ°°μ΄μ μ΄λ»κ² μμ±ν μ§ κ³ λ―Όνκ³ , μ΄μ dpκ°λ€μ μ΄λ»κ² νμ©ν μ§ κ³ λ―Όν΄λ³΄λ©΄ λ΅μ΄ 보μ΄λ κ² κ°λ€.
κ·Έλλ μ μλ μ€λ₯΄λ©΄, κ²½μ°μ μλ₯Ό μ§μ μ μ΄λ³΄λ©° κ·μΉμ μ°ΎμΌλ©΄ ν΄κ²°μ΄ λλ κ² κ°λ€.
λλ dp[][] 2μ°¨μ λ°°μ΄μ μκ°νλ€.
μ무리 μκ°ν΄λ 1μ°¨μ λ°°μ΄λ‘λ ν΄κ²°ν μ μμ κ²μ΄λΌ νλ¨νλ€.
μλνλ©΄ μ μ체μ λν λ³νλ μκ³ μμ κ°―μμ λν λ³νλ μκΈ°κΈ° λλ¬Έμ΄λ€.
κ±°λμ λ―Έ νκ³ μ΄λ»κ² ν΄κ²°νλμ§ μ€λͺ ν΄λ³΄κ² λ€!
dp[i][j]μλ iλ₯Ό jκ°λ‘ νννλ κ²½μ°μ μλ₯Ό κΈ°λ‘ν κ²μ΄λ€.
dp[1][ ] μ κ²½μ°μλ
dp[1][j] = jκ° μ±λ¦½νλ€.
1μ 1κ°λ‘ ννν μ μλ λ°©λ²μ 1 ( 1 )
1μ 2κ°λ‘ ννν μ μλ λ°©λ²μ 2(0+1 , 1+0)
1μ 3κ°λ‘ ννν μ μλ λ°©λ²μ 3(0+0+1 , 0+1+0 , 1+0+0)
……
1μ nκ°λ‘ ννν μ μλ λ°©λ²μ nκ°μ΄λ€.
dp[2][j] λ₯Ό μ΄ν΄λ³΄μ
2λ₯Ό 1κ°λ‘ ννν μ μλ κ²½μ°μ μ 1 ( 2 )
2λ₯Ό 2κ°λ‘ ννν μ μλ κ²½μ°μ μ 3( 0+2 , 1+1, 2+0 )
2λ₯Ό 3κ°λ‘ ννν μ μλ κ²½μ°μ μ 6( 0+0+2 , 0+1+1, 0+2+0, 1+0+1, 1+1+0, 2+0+0 )
μ¬κΈ°μ μ€μν μ 0+0+2 , 0+1+1 , 0+2+0 μ κ²½μ°μ μλ₯Ό 보면
0+2 μμ λ€μ 2λ₯Ό μ«μ 2κ°λ‘ ννν μ μλ κ²½μ°μ μμ΄λ€. μ¦ dp[2][2]μμ νμΈν μ μλ€.
κ·Έλ¦¬κ³ 1+0+1, 1+1+0 μ 1+1μμ λ€μ 1μ 2κ°λ‘ ννν μ μλ κ²½μ°μ μκ° λλ€.
μ¦, dp[1][2] μμ μ μ μλ€.
λ§μ§λ§ 2+0+0μ 2λ₯Ό 4κ°λ‘ ννν μ μλ κ²½μ°μ μ μλ 2+0+0+0 μΌλ‘ ννλ κ²μ΄κ³
2λ₯Ό 5κ°λ‘ ννν μ μλ κ²½μ°μ μμλ 2+0+0+0+0 μΌλ‘ ννλ κ²μ΄λ€. λ€μ κ°λ¨ν +0μ μΆκ°νλ κ²½μ°μ μλ 무쑰건 μ‘΄μ¬ν κ²μ΄λ€.
μ΄ κ°μ μν©λλ¬Έμ 맀 νλ§λ€ dpλ‘ ννλλ κ² μ΄μΈμ κ²½μ°μ μ 1κ°λ 무쑰건 μ‘΄μ¬νλ€.
μ΄μ μ΄λμ λ ν¨ν΄μ΄ 보μΈλ€.
μ΄μ , dp[n][k] λ‘ μκ°μ ν΄λ³΄μ
dp[n][1] μ 무쑰건 1κ°μ΄λ€. +0μ λΆμΌ μλ μκ³ nμ 1κ°λ‘ νννλ κ²½μ°μ μλ n νλμ΄λ€.
dp[n][2] λ 0 + n , 1+(n-1) · · · · · · · (n-1) +1 , n +0 μΌ κ²μ΄λ€.
μ΄λ nμ 1κ°λ‘ νννλ κ²½μ°μμ + n-1μ 1κ°λ‘ νννλ κ²½μ°μ μ + · · · · · ·+ 1μ 1κ°λ‘ νννλ κ²½μ°μ μ + 맀 νλ§λ€ μΆκ°λλ κ²½μ°μ μ(n+0) κ° λ κ²μ΄λ€.
μ¦, dp[n][2] = dp[n][1] + dp[n-2][1] + · · · · · · · ·+dp[1][1] +1 μ΄ λλ€.
dp[n][3]λ μμ λΉμ·νλ€. 0+n μ μ«μ 3κ°λ‘ λ§λλ €λ©΄ nμ 2κ°λ‘ νννλ κ²½μ°λ‘ λ°κΏμΌ μ«μ 3κ°λ‘ ννμ΄ λ κ²μ΄λ€.
λν, 1+(n-1) μ μ«μ 3κ° μ‘°ν©μΌλ‘ λ§λλ €λ©΄ n-1μ 2κ°λ‘ νννλ κ²½μ°λ‘ λ°κΏμΌ νλ€. · · · · · · · (n-1)+1 μ μ«μ 3κ° μ‘°ν©μΌλ‘ λ§λλ €λ©΄ 1μ 2κ°λ‘ νννλ κ²½μ°λ‘ λ°κΏμΌ νλ€.
κ·Έλ¦¬κ³ λ§μ§λ§μΌλ‘ n + 0 + 0 μ κ²½μ°μ μκ° μκΈ΄λ€.
μ¦ dp[n][3] = dp[n][2] + dp[n-1][2] · · · ·+dp[1][2] +1 μ΄ λλ€.
μ΅μ’ μ μΌλ‘ dp[n][k] = dp[n][k-1]+dp[n-1][k-1]+ · · · · ·+dp[1][k-1] +1 μ΄ λ¨μ μ μ μλ€.
μ΄μ μ νμμ ꡬνμΌλ, μ½λλ‘μ ꡬννλ©΄ λλ€!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int N = Integer.valueOf(input[0]);
int K = Integer.valueOf(input[1]);
long [][]dp=new long [N+1][K+1];
for(int i=1;i<=N;i++) {
for(int j=1;j<=K;j++) {
dp[i][j]=1; //μ΅μ 1κ°μ κ²½μ°μ μλ μμΌλ―λ‘ 1κ°λ‘ λͺ¨λ μ΄κΈ°ν
for(int k=1;k<=N;k++) {
dp[i][j]+=dp[k][j-1]%1000000000;//ꡬν μ νμ
}
}
}
System.out.println(dp[N][K]%1000000000);
}
}