[Java] 백준 2225번 합분해

다이나믹 프로그래밍 문제입니다.

N을 K개의 수로 만드는 경우의 수를 구해야 합니다.
수는 1~N이 있고 중복해서 사용할 수 있습니다.

2차원 DP배열을 만들어줍니다.
dp[K개][N값]

dp배열에는 a개의 개수가 있을때 b값을 만들 때 경우의 수를 저장합니다.

for (int i = 2; i <= m; ++i) {
  for (int j = 0; j <= n; ++j) {
    dp[i][j] = dp[i - 1][j];
    dp[i][j] %= 1_000_000_000;
    if (j < n) {
      dp[i - 1][j + 1] += dp[i - 1][j];
      dp[i - 1][j + 1] %= 1_000_000_000;
    }
  }
}

 

최종적으로 계산 된 경우의 수를 출력해주었습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

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

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

    for (int i = 2; i <= m; ++i) {
      for (int j = 0; j <= n; ++j) {
        dp[i][j] = dp[i - 1][j];
        dp[i][j] %= 1_000_000_000;
        if (j < n) {
          dp[i - 1][j + 1] += dp[i - 1][j];
          dp[i - 1][j + 1] %= 1_000_000_000;
        }
      }
    }

    bw.write(dp[m][n] + "\n");
    bw.close();
  }
}