[JAVA] 백준 2225번 【합분해】

---

이번 문제는 혼자 풀어서 매우 뿌듯했던 문제!

 

포기하지 않아서 결국 풀 수 있었다~

 

DP문제는 Dp배열을 어떻게 생성할지 고민하고, 이전 dp값들을 어떻게 활용할지 고민해보면 답이 보이는 것 같다.

 

그래도 정 안떠오르면, 경우의 수를 직접 적어보며 규칙을 찾으면 해결이 되는 것 같다.

 

나는 dp[][] 2차원 배열을 생각했다.

 

아무리 생각해도 1차원 배열로는 해결할 수 없을 것이라 판단했다.

 

왜냐하면 수 자체에 대한 변화도 있고 수의 갯수에 대한 변화도 생기기 때문이다.

 

거두절미 하고 어떻게 해결했는지 설명해보겠다!

 

dp[i][j]에는 i를 j개로 표현하는 경우의 수를 기록할 것이다.

 

---

dp[1][ ] 의 경우에는

 

dp[1][j] = j가 성립한다.

1을 1개로 표현할 수 있는 방법은 1 ( 1 )

1을 2개로 표현할 수 있는 방법은 2(0+1 , 1+0)

1을 3개로 표현할 수 있는 방법은 3(0+0+1 , 0+1+0 , 1+0+0)

……

1을 n개로 표현할 수 있는 방법은 n개이다.

 

---

dp[2][j] 를 살펴보자

 

2를 1개로 표현할 수 있는 경우의 수 1 ( 2 )

2를 2개로 표현할 수 있는 경우의 수 3( 0+2 , 1+1, 2+0 )

2를 3개로 표현할 수 있는 경우의 수 6( 0+0+2 , 0+1+1, 0+2+0, 1+0+1, 1+1+0, 2+0+0 )

 

여기서 중요한 점 0+0+2 , 0+1+1 , 0+2+0 의 경우의 수를 보면

0+2 에서 뒤에 2를 숫자 2개로 표현할 수 있는 경우의 수이다. 즉 dp[2][2]임을 확인할 수 있다.

 

그리고 1+0+1, 1+1+0 은 1+1에서 뒤에 1을 2개로 표현할 수 있는 경우의 수가 된다.

즉, dp[1][2] 임을 알 수 있다. 

 

마지막 2+0+0은 2를 4개로 표현할 수 있는 경우의 수 에는 2+0+0+0 으로 표현될 것이고
2를 5개로 표현할 수 있는 경우의 수에는 2+0+0+0+0 으로 표현될 것이다. 뒤에 간단히 +0을 추가하는 경우의 수는 무조건 존재할 것이다.

 

이 같은 상황때문에 매 항마다 dp로 표현되는 것 이외에 경우의 수 1개는 무조건 존재한다.

 

이제 어느정도 패턴이 보인다.

 

---

 

이제, dp[n][k] 로 생각을 해보자

 

dp[n][1] 은 무조건 1개이다. +0을 붙일 수도 없고 n을 1개로 표현하는 경우의 수는 n 하나이다.

 

 

dp[n][2] 는 0 + n , 1+(n-1) · · · · · · · (n-1) +1 , n +0 일 것이다.  

이는 n을 1개로 표현하는 경우의수 + n-1을 1개로 표현하는 경우의 수 + · · · · · ·+ 1을 1개로 표현하는 경우의 수 + 매 항마다 추가되는 경우의 수(n+0) 가 될것이다.

 

즉, dp[n][2] = dp[n][1] + dp[n-2][1] + · · · · · · · ·+dp[1][1] +1 이 된다.

 

 

dp[n][3]도 위와 비슷하다. 0+n 을 숫자 3개로 만드려면 n을 2개로 표현하는 경우로 바꿔야 숫자 3개로 표현이 될 것이다.

 

또한, 1+(n-1) 을 숫자 3개 조합으로 만드려면 n-1을 2개로 표현하는 경우로 바꿔야 한다. · · · · · · · (n-1)+1 을 숫자 3개 조합으로 만드려면 1을 2개로 표현하는 경우로 바꿔야 한다.

그리고 마지막으로 n + 0 + 0 의 경우의 수가 생긴다.

 

 

즉 dp[n][3] = dp[n][2] + dp[n-1][2] · · · ·+dp[1][2] +1 이 된다.

 

최종적으로 dp[n][k] = dp[n][k-1]+dp[n-1][k-1]+ · · · · ·+dp[1][k-1] +1 이 됨을 알 수 있다.

 

이제 점화식을 구했으니, 코드로서 구현하면 된다!

 

---

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

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.valueOf(input[0]);
		int K = Integer.valueOf(input[1]);
		
		long [][]dp=new long [N+1][K+1];
		
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=K;j++) {
				dp[i][j]=1; //최소 1개의 경우의 수는 있으므로 1개로 모두 초기화
				for(int k=1;k<=N;k++) {
					dp[i][j]+=dp[k][j-1]%1000000000;//구한 점화식
				}
			}
		}
		
		System.out.println(dp[N][K]%1000000000);
	}
}