[백준,BOJ 2225] 합분해( JAVA 구현)

-내 생각

  처음 문제를 접했을 때는 어떻게 접근해야 할지 감이 잡히지 않았다. 그러나 조금 생각해 봤더니 어느 정도 길이 보였다. 처음 접근한 방법은 각 경우의 수를 따져보는 것이었는데, 이 문제의 경우는 자리 수가 고정되어 있는 것이 아닌, 입력값에 따라 자릿수가 달라지기 때문에 각 자릿수에 따라 경우의 수를 따져야 될 것 같았다. 예를들어 예제 입력의 경우 자리 수가 2자리 이기 때문에, 자리 수가 1인 경우를 따진 후 자리 수가 한 자리 늘어났을 때 이전 자리 수의 경우의 수를 활용하는 방식으로 표를 완성할 수 있었다. 

 

-해법

  위의 방식으로 접근해보아야겠다는 생각을 한 후 경우를 따져 보았다. 우선 n이 4이고 k가 3일 때를 아래의 표를 보면서 따져보자. 첫 번째로 자리 수가 한 개일 경우는 n보다 작은 수로 만들 수 있는 경우가 자기 자신밖에 존재하지 않는다.

 

n/k	1	2	3
0	1
1	1
2	1
3	1
4	1

  그렇다면 자리 수가 2개일 경우는 어떨까? n이 다른 값들은 모르겠지만 n이 0인 경우는 확실하다. 0+0한 개가 존재하게 된다. 이는 자리 수에 상관이 없다는 것을 알 수 있을 것이다. k가 3일 경우 n이 0이면 0+0+0, k가 4일 때, n이 0이면 0+0+0+0... 식으로 각 자릿수마다 1개밖에 존재하지 않게 된다. 여기까지의 상태가 해당 표의 초기값이 된다.

n/k	1	2	3
0	1	1	1
1	1
2	1
3	1
4	1

  그럼 초기화가 완료된 상태에서 n이 다른 값일 경우를 계산해야 하는데, 한눈에 알아보기 쉽게 우선 손으로 만들 수 있는 n이 1인 경우는 직접 채워보자. n이 1이고 k가 2일 경우, 0과 1로 1을 만들어야 하는데, 이때의 경우의 수는 0+1과 1+0이 존재한다. 자리 수가 3일 경우는 1+0+0, 0+1+0, 0+0+1로 3개가 존재한다. (이 경우도 자리 수를 증가시키면서 따져보면 n이 1일 때는 결국 자리 수와 경우의 수가 같다는 것을 알 수 있다.)

n/k	1	2	3
0	1	1	1
1	1	2	3
2	1
3	1
4	1

  이제 n이 2일 때를 보자. n이 2일 때, k가 2인 경우는 0+2와 2+0, 그리고 1+1이라는 사실을 알 수 있다. 그렇다면 이전에 구해놓은 경우의 수를 어떻게 활용하면 좋을까? 이 부분에 대해서 참고하면 좋을만한 내용이 있는데, n이하의 숫자를 가지고 n을 만들기 위해서는 각 숫자들이 짝을 짓고 있다는 것을 알 수 있다. 예를 들어, n이 5인 경우, 0,1,2,3,4,5로 5를 만들어야 하는데, 0 - 5가 짝이고, 1 - 4가 짝이고, 2 - 3이 짝으로 각 짝들로 n을 만들 수 있다는 것을 알 수 있다. 

 

  다시 표로 돌아와서 k가 2고 n이 2일 때, +는 항상 고정이므로 배제하고 생각한다면 숫자의 조합이 2-0, 1-1, 0-2가 된다는 것을 알 수 있다. 이 말인즉슨, 끝 자리를 기준으로 생각했을 때, 끝자리가 0일 경우 2를 만들기 위해서는 앞자리의 끝자리가 2가 돼야 한다. 1일 경우는 1이, 2일 경우는 0이 되야한다. 이 세 가지의 경우를 모두 합한 것이 2를 만들기 위한 경우의 수가 되게 된다. 즉, 0부터 자기 자신까지의 행을 빼준 뒤, 이전 자리 수의 경우의 수들을 더하는 것이다. 이런 식으로 표를 채워보면

 

n/k	1	2	3
0	1	1	1
1	1	2	3
2	1	dp[n-0][1] + dp[n-1][1] + dp[n-2][1] = 3	dp[n-0][2] + dp[n-1][2] + dp[n-2][2] = 6
3	1	4	10
4	1	5	15

  와 같은 표가 완성되게 되고 결국 dp [n][k]의 값을 출력해주면 정답이 된다.

 

점화식은 아래와 같다.

dp [i][k] = dp [i-0][k-1] + dp [i-1][k-1] + dp [i-2][k-1].... + dp [i-i][k-1]

import java.util.*;
import java.math.*;
public class Main {
	
	static long dp[][] ;
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int k =sc.nextInt();
		
		dp = new long[n+1][k+1];
		
		for(int i=1;i<=k;i++) { //dp배열 초기화
			dp[0][i] =1;
			if(n>0)
				dp[1][i] =i;
		
		}
		for(int i=1;i<=n;i++) { // dp배열 초기화
			dp[i][1]=1;
		}
		
		for(int i=2;i<=n;i++) { 
			for(int j=2;j<=k;j++) { 
				for(int g=0;g<=i;g++) { // 행과 열을 고정해두고 0부터 i까지 반복한다.
					dp[i][j] += dp[i-g][j-1] %1000000000; // 나머지로 저장 범위초과 우려
				}
				dp[i][j] %= 1000000000; // 나머지로 저장 범위초과 우려
				
			}
			
		}
		
		System.out.println(dp[n][k] % 1000000000 ); //출력시에도 나머지로 출력한다.
				
		
		
			
	}
	
}