[백준]2225: 합분해 - JAVA

[백준]2225: 합분해

www.acmicpc.net/problem/2225

2225번: 합분해

 

풀이

(dp는 너무 어려워..휴우)

 

dp함수를 이차원 배열을 사용하여 표현하였다. 각각의 인덱스는 dp[n][k]일때 0부터 n까지의 정수로 k를 표현할 수 있는 경우의 수를 저장하도록 하였다.

 

우선 예제입력인 20,2의 경우의 수를 모두 찾아 보았다.

0, 20	20, 0
1, 19	19, 1
2, 18	18, 2
3, 17	17, 3
4, 16	16, 4
5, 15	15, 5
6, 14	14, 6
7, 13	13, 7
8, 12	12, 8
9, 11	11, 9
10, 10

더하는 순서가 다르면 다른 경우로 계산하기 때문에 0, 20은 20, 0과 다른 경우이다. 이때 이 둘은 dp[0][1] + dp[20][1]로 표현할 수 있다. 

마찬가지로 1, 19와 19, 1또한 dp[1][1] + dp[19][1]로 표현할 수 있다.

 

이때 필요한 dp배열을 모두 나열해 보면 다음과 같다.

dp[0][1] + dp[1][1] + dp[2][1] + dp[3][1] + dp[4][1] + dp[5][1] + dp[6][1] + dp[7][1] + dp[8][1] + dp[9][1] + dp[10][1] + dp[11][1] + dp[12][1] + dp[13][1] + dp[14][1] + dp[15][1] + dp[16][1] + dp[17][1] + dp[18][1] + dp[19][1] + dp[20][1] = 21

 

하지만 아직까지는 점화식을 어떻게 작성해야 할지 감이 안온다. 그래서 작은 수 부터 경우의수를 하나씩 계산해 보며 규칙을 찾아 보았다.

우선 n이 0일때를 보면 k가 0일때를 제외하곤 항상 경우의 수가 1이다.

dp	경우의 수	가능한 경우
dp[0][0]	0	없다.
dp[0][1]	1	0
dp[0][2]	1	0+0
dp[0][3]	1	0+0+0

n이 1이면 다음과 같다. 

dp	경우의 수	가능한 경우
dp[1][0]	0	없다
dp[1][1]	1	1
dp[1][2]	2	0+1, 1+0
dp[1][3]	3	0+0+1, 0+1+0, 1+0+0

n이 2이면 다음과 같다.

dp	경우의 수	가능한 경우
dp[2][0]	0	없다
dp[2][1]	1	2
dp[2][2]	3	1+1, 2+0, 0+2
dp[2][3]	6	0+1+1, 1+0+1, 1+1+0, 2+0+0, 0+2+0, 0+0+2

n이 3이면 다음과 같다.

dp	경우의 수	가능한 경우
dp[3][0]	0	없다
dp[3][1]	1	3
dp[3][2]	4	1+2, 2+1, 0+3, 3+0
dp[3][3]	10	1+1+1, 0+1+2, 0+2+1, 1+0+2, 1+2+0, 2+0+1, 2+1+2, 0+3+0, 0+0+3, 3+0+0

 

이번엔 위의 표들을 합쳐서 만들어 보았다.

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

표를 완성하고 보니 규칙이 눈에 들어왔다. (빨간색으로 칠해진 부분은 처음에 초기화가 필요한 부분이다.)

파란색으로 칠해진 위치를 보면 dp[3][2]에 해당하고 이는 dp[3][1]과 dp[2][2]를 합한 값이 된다. 나머지 경우도 모두 해당된다.  

 

주어진 예제인

dp[20][2] = dp[20][1] + dp[19][2]가 될 것이고

dp[19][2] = dp[19][1] + dp[18][2]이 될 것이다.

dp[18][2] = dp[18][1] + dp[17][2]가 될 것이고

... dp[1][2] = dp[1][1] + dp[0][2]까지 될 것이다. 

이를 다 나열해보면 결국 처음에 계산해 보았던 필요한 dp배열을 모두 포함하는 것을 알 수 있다. 

 

점화식을 구해보면 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]이다.

이제 코드로 구현해 주기만 하면 된다..!

 

코드

import java.util.*;
 
public class Main {    
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        long mod = 1000000000;
        
        int n = scan.nextInt();
        int k = scan.nextInt();
        
        long dp[][] = new long[n + 1][k + 1];
        for(int i = 0; i < n + 1; i++) {
            dp[i][1] = 1; //정수 1개를 더해서 i를 만드는 경우의 수는 하나밖에 없다. 
        }
        for(int i = 1; i < k + 1; i++) {
            dp[0][i] = 1; //정수 0을 i개 사용해서 0을 만드는 경우의 수는 0, 00, 000... 하나밖에 없다.
        }
        
        
        for(int i = 1; i <= n; i++) {
            for(int j = 2; j <= k; j++) {
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % mod;
            }
        }
        System.out.println(dp[n][k] % mod);
    }    
}