[백준] 2225 합분해 [자바]

 

 

---

https://hongjw1938.tistory.com/63

알고리즘 풀이 - 백준 2225(합분해, DP)

 

※. dp[N][K] (정수 k개를 더해서 N을 만듦)

 

※. 마지막에 더하는 숫자가 k 일 때 N을 만드는 경우의 수는 dp[N][k포함] = dp[N-k][이전횟수(-1)]

 

---

 

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

public class Main {
	static long mod = 1_000_000_000;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		long[][] dp = new long[N+1][K+1];
		for(int i = 0; i <= N; i++) {
			dp[i][1] = 1;
		}
		
		for(int i = 2; i <= K; i++) {
			for(int j = 0; j <= N; j++) {
				for(int k = 0; k <= j; k++) { //k를 더해서 j 만듦
					dp[j][i] += dp[j-k][i-1];
					dp[j][i] %= mod;
				}
			}
		}
		System.out.println(dp[N][K]);
	}
}