[백준] 2225: 합분해

문제

문제 풀이

• N = 1일 경우, 정수 K개를 더해서 N이 되는 경우의 수는 다음과 같다.
  k = 1 -> 1
  - dp[1][1] = 1
  k = 2 -> 0 + 1, 1 + 0
  - dp[1][2] = 2
  k = 3 -> 0 + 0 + 1, 0 + 1 + 0, 1 + 0 + 0
  - dp[1][3] = 3

  dp[1][i] = i

• K = 1일 경우, 정수 N이 되는 경우는 N 하나를 더하는 경우의 수 밖에 없다.

  dp[i][1] = 1

• dp[N][K]
  - K-1개를 이용하여 N을 만드는 방법에 0을 더하면 K개를 사용한 것으로 dp[N][K-1]의 경우의 수를 더해준다.
  - K개를 이용하여 N-1을 만드는 방법에 1을 더하면 N이 되므로
  dp[N-1][K]의 경우의 수를 더해준다.

  dp[N][K] = dp[N][K-1] + dp[N-1][K]

코드

import java.util.Scanner;

public class ANS2225 {

    static int N, K;
    static long dp[][];
    static int mod =  1000000000;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        K = sc.nextInt();

        //dp선언 및 초기화
        dp = new long[N+1][K+1];

        for(int j = 1 ; j <= K; j++){
            dp[1][j] = j;
        }

        for(int i = 1; i <= N; i++){
            dp[i][1] = 1;
        }


        for(int i = 2 ; i <= N; i++){
            for(int j = 2 ; j <= K; j++){

                dp[i][j] = (dp[i][j-1] + dp[i-1][j])%mod;

            }
        }

        System.out.println(dp[N][K]);


    }
}