[백준 코딩테스트] 2225번 합분해

풀이

n = 1

• k=1 : 1가지
• k=2 : 2가지(0+1, 1+0)
• k=3 : 3가지(0+0+1, 0+1+0, 1+0+0)

위와 같은 dp 배열을 얻을 수 있다.

n = 2

• k=1 : 1가지
• k=2 : 3가지(0+2, 2+0, 1+1)
• k=3 : 6가지(0+0+2, 0+2+0, 2+0+0, 1+1+0, 1+0+1, 0+1+1)
  
  이를 통해 점화식 dp[n][k] = dp[n-1][k] + dp[n][k-1]을 도출할 수 있다.

내 코드

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

public class Main {
    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());

        int[][] dp = new int[n+1][k+1];


        // k가 0일 때 경우의 수 0으로 초기화, k가 1일 때 경우의 수 1로 초기화(자기자신만이 n을 만들 수 있음)
        for(int i=0; i<=n; i++){
            dp[i][0] = 0;
            dp[i][1] = 1;
        }

        // n이 1일 때 경우의 수는 K개, 1을 어떻게 배치하느냐에 따라 달라짐
        for(int i=0; i<=k; i++){
            dp[1][i] = i;
        }

        for(int i=2; i<=n; i++){
            for(int j=2; j<=k; j++){
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000000;
            }
        }
        
        System.out.println(dp[n][k]);     

    }    

       
}