백준|2225번|합분해

문제설명
숫자 N과 K를 입력받고 정수 K개를 더 해 N을 만들 수 있는 경우의 수를 구하고 그 수를 1000000000으로 나눈 나머지를 출력하는 문제입니다.

작동 순서
1. 숫자 N과 K를 입력받습니다.
2. K가 1일때는 모든 숫자를 만드는 방법이 한가지뿐이고 K가 2일때는 모든 숫자를 만드는 방법은 N+1가지뿐이므로 dp[1]과 dp[2]에 값을 입력해줍니다.
3. dp[K][N]=dp[K-1][N]+dp[K][N-1]이므로 두 값을 더하고 그 수를 1000000000으로 나눈 나머지를 입력해줍니다.
4. 입력된 N과 K에 맞는 값을 출력해줍니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

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.parseInt(input[0]), K=Integer.parseInt(input[1]);
        int[][] dp=new int[201][201];
        Arrays.fill(dp[1], 1);
        for(int i=0;i<N+1;i++){
            dp[2][i]=i+1;
        }
        for(int i=3;i<K+1;i++){
            dp[i][0]=1;
            for(int j=1;j<N+1;j++){
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000000;
            }
        }
        System.out.print(dp[K][N]);
    }
}