[백준] 2225 - 합분해 (java)

2225번: 합분해

---

 

문제

두 정수 n과 k를 입력받는다

여기서 n은 만드려고 하는 수, k는 n을 만들기 위해 사용하는 수의 갯수이다.

0부터 n까지 정수 k개를 더해서 합이 n이 되는 경우의 수를 구한다.

 

만약 입력값이 4 2 라면 

1 3

3 1

4 0

0 4

2 2

이렇게 5가지가 된다

 

 

 

문제 풀이

우리가 구하는 경우의 수를 k와 n에 따라 dp에 저장하기 위해 dp[k+1][n+1] 배열을 만들었다.

 

1. n = 0일때 (만드려는 수가 0)

만드려는 수(n)가 0이면 자릿수(k)가 어떻게 되던지 1가지 방법이 나온다.

(n = 0 , k = 3 이면 0 0 0으로 한가지 n = 0, k = 4면 0 0 0 0으로 한가지)

 

2. k = 1일때

1개의 숫자 조합으로 n을 만드는 방법은? 본인 숫자를 쓰는 방법 단 하나이다.

 

3. k = 2일때

두 가지 숫자를 조합하여 숫자를 만들어보자

 

n=1,k=2

(1,0) (0,1)

dp[2][1] = 2

 

n=2,k=2

(0,2) (2,0) (1,1)

dp[2][2] = 3

...

n=5,k=2

(5,0) (0,5) (2,3) (3,2) (4,1) (1,4) 

dp[2][5] = 5

 

위에서 구한 숫자를 보기쉽게 표에 적어보면 아래와 같아진다.

	n = 0	n = 1	n = 2	n = 3	n = 4	n = 5	n = 6
k = 1	1	1	1	1	1	1	1
k = 2	1	2	3	4	5	6	7
k = 3	1
k = 4	1

 

그리고 k=3일때 n=1을 구해보면 (1,0,0) (0,1,0) (0,0,1) 3가지가 나온다.

	n = 0	n = 1	n = 2	n = 3	n = 4	n = 5	n = 6
k = 1	1	1	1	1	1	1	1
k = 2	1	2	3	4	5	6	7
k = 3	1	3
k = 4	1

 

위 표에서 dp[k][n]를 구하기 위해서 dp[k][n-1] + dp[k-1][n] 점화식이 된다는 것을 볼 수있다

• . dp[k][n] = dp[k][n-1] + dp[k-1][n]

위 점화식으로 전체 표를 채워보면

	n = 0	n = 1	n = 2	n = 3	n = 4	n = 5	n = 6
k = 1	1	1	1	1	1	1	1
k = 2	1	2	3	4	5	6	7
k = 3	1	3	6	10	15	21	28
k = 4	1	4	10	20	35	56	84

예제와 같이 n=6 k=4 일때 84라는 답이 나온다

 

 

주의할점

dp에 경우의 수를 넣을때 1,000,000,000 으로 나누어서 넣는 것을 잊지말자...

 

---

import java.util.Scanner;

public class B2225 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        // k = 더하는 수의 갯수, n = 만드려는 목표값
        int[][] dp = new int[k+1][n+1];

        for (int i = 0; i <= n; i++) {
            dp[1][i] = 1;
        }

        for (int i = 2; i <= k; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
                dp[i][j] %= 1000000000;
            }
        }
        System.out.println(dp[k][n]);
    }
}