[백준] 2225번 합분해

https://www.acmicpc.net/problem/2225

2225번: 합분해

 

N = 6, K = 4 일 때 경우의 수

0	+ 6	3번 더해서 0일 때
1	+ 5	3번 더해서 1일 때
2	+ 4	3번 더해서 2일 때
3	+ 3	3번 더해서 3일 때
4	+ 2	3번 더해서 4일 때
5	+ 1	3번 더해서 5일 때
6	+ 0	3번 더해서 6일 때

 

dp[4][6] = dp[3][0] + dp[3][1] + dp[3][2] + dp[3][3] + dp[3][4] + dp[3][5] + dp[3][6]

점화식 : dp[K][N] = dp[K-1][N]  

 

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

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long mod = 1000000000;

        int n = sc.nextInt();
        int k = sc.nextInt();

        long dp[][] = new long[201][201];
        for(int i = 0; i <= k; i++) {
        	dp[i][0] = 1; // 정수 0을 i개 사용해서 0을 만드는 경우의 수는 0 한개밖에 없음
        }

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