[백준 - 2225번] 합분해 - 자바(JAVA) 정리 및 해설 - 1일 1DP 9일차

2225번: 합분해

어떤식으로 풀었나?

일단 이문제는 N의 정수를 K개를 가지고 만드는 경우를 찾아야합니다. 

가장 쉽게 생각할 경우는 정수 1개를가지고 N을 만드는 경우와 정수 2개를 가지고 N을 만드는 경우인데요.

정수 1개를가지고 N을 만드는 경우는 무슨 정수든간에 1개

정수 2개를 가지고 N을 만드는 경우는 0~N까지 한가지 경우씩 있기때문에 N+1가지가 존재합니다.

이런 N과 K를 동시에 가지고 있어야하기때문에 DP배열을 2차원 배열로 만들어야합니다. 

저의 경우 DP[K][N]식으로 배열을 만들어줬습니다. 즉 DP[1][3] 이라면, 3을 만들기위해서 정수 1개가지고 만드는 경우의 수라고 생각하면 됩니다.

정수 3개이상 부터 점화식을 이용해서 문제를 풀어야하는데, 가장 생각해봄직한 것은

3개를 가지고 1을 만들어야하는 경우라면,

한 정수를 미리 지정한 뒤에, 정수 2개의 경우로 계산해버리는 방식입니다. N을 만들수 있는 모든 경우를 다 합해줘야합니다.

직접적으로 생각해보면 0을 선택하고 2개의 정수를가지고 1을 만든 경우의 수와 1을 선택하고 2개의 정수를가지고 0을 만든 경우의 수를 합해주면 문제가 없겠죠. 

즉, DP[3][1] = DP[2][0]  +DP[2][1]로 수식으로 바꿔서 생각할 수 있겠죠. 

결론적으로 구하려는 K개의 N값을 구하기 위해서는 그 값의 K-1개의 0~N까지의 모든 경우의 합을 만들어주면 됩니다.

 

/** 2020. 2. 27. 오후 5:17:32
 * @author ventulus95
 */
package codeBaekJoon;

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

public class No2225_sumDiv {
	
	static long dp[][] = new long[201][201];

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String tc = br.readLine();
		StringTokenizer st = new StringTokenizer(tc, " ");
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		for(int i=0; i<201; i++){
			dp[i][0] = 1;
			dp[1][i] = 1;
		}
		for(int i=1; i<201; i++){
			dp[2][i] = i+1;
		}
		for(int i=3; i<201; i++){
			for(int j=1; j<201; j++){
				for(int k1=0; k1<=j; k1++){
					dp[i][j]+= dp[i-1][j-k1]%1000000000;
				}
			}
		}
		System.out.println(dp[k][n]%1000000000);
	}
}