백준 2225번

2225번: 합분해

2개의 숫자 N과 K가 주어진다.

0~N까지의 숫자 범위 내에서 K개의 숫자를 이용하여 N을 만들  수 있는 경우의 수를 구하는 프로그램이다.

숫자는 중복으로 사용가능 하며 덧셈의 순서가 바뀐 경우에도 다른 경우의 수에 포함시킨다. (1+2, 2+1은 다르다)

 

---

나의 풀이

2차원 배열을 이용하여 숫자 2개를 사용하여 연산하는 경우의 수를 다음에 숫자 3개를 이용하여 N을 만드는 경우의 수를 

구할 때 사용하면 될 거 같다고 생각하여 표를 그려 정리하였다.

 

arr	0	1	2	3	4
dp[0][n]	1	1	1	1	1
dp[1][n]

 

dp [0][n]은 arr [n]의 원소를 제일 먼저 사용하여 숫자 2개를 사용하여 연산을 하는 경우의 수를 저장하고 있다.

0+4, 1+3, 2+2, 3+1, 4+0의 경우의 수가 가능하기 때문에  dp [0][n]에 모든 값에 1로 세팅된다.

이 부분에서 숫자 2개를 사용하여 연산을 하는 경우의 수는 n+1개의 경우의 수를 가진다는 규칙을 찾았다.

 

arr	0	1	2	3	4
dp[0][n]	1	1	1	1	1
dp[1][n]	5	2	2	2	1

이제 3가지 숫자를 이용하여 연산을 진행하는 경우의 수를 찾기 위해 2가지 숫자를 이용한 경우의 수를 담고 있는 dp [0][n]을 활용해

dp [1][n]을 구하고자 했다.

 

위와 같은 식이 나온 이유는 다음과 같다.

 

0으로 시작하면서 3가지 숫자를 이용하여 4를 만들 수 있는 경우의 수

0+0+4, 0+1+3, 0+2+2, 0+3+1, 0+4+0 = 총 5개

이렇게 개수가 나와서 dp [i][0] = dp [i-1][0] +... dp [i-1][n]의 점화식을 하나 작성을 하였다.

 

1로 시작하면서 3가지 숫자를 이용하여 4를 만들 수 있는 경우의 수

1+1+3, 1+3+1 = 총 2개

이와 같이 경우의 수가 나와서 dp [i][1] ~ dp [i][n-1] = dp [i-1] + 1의 점화식을 작성하였다.

 

마지막으로 4는 뒤에 더할 수 있는 수가 0밖에 없기 때문에 몇 개의 숫자를 더하던 0밖에 더하지 못한다.

그래서 dp [i][n] = 1의 점화식을 작성하였다.

 

이렇게 점화식을 작성하고 내가 만든 점화식에 푹 빠져 생각의 구렁텅이에 갇혔다고 해야 되나 다른 개념을 생각하지 않으려고 했다.

하지만 반례가 너무나도 많았다. 내가 만든 점화식은 2가지 숫자를 이용한  연산식만 가지고 3가지, 4가지를 이용한 숫자의 연산을 하려고 하기 때문에 새로 등장하는 케이스를 전혀 다루지 못했다. 예를 하나 들면 숫자 4개를 사용하여 4를 만들고자 할 때 1+1+1+1과 같은 식을 

경우의 수에 포함할 수가 없다. 결국은 해답을 찾지 못하고 정답을 보기로 했다!...

 

---

정답 점화식

arr	1	2	3	4	5
dp[0][n]	1	1	1	1	1
dp[1][n]	2	3	4	5	6
dp[2][n]	3	6	10	15	21

 

정답점화식은 이용하여 표를 작성하면 다음과 같이 나온다.

내가 했던 사고방식과는 비슷하지만 dp들을 작성할 때 개념이 다르다.

 

dp [0][n]에는 숫자 2개를 이용하여 arr [n]의 원소 값을 만드는 경우의 수를 저장한다.

나는 dp[0][n]에 주어진 숫자 n을 만드는 경우의 수를 저장하여서 접근하는 방법이 달랐다.

 

2가지 숫자를 이용하여 3을 구하는 경우의 수를 예로 들면

2가지 숫자를 이용하여 2를 구하는 경우의 수 = 1+1, 0+2, 2+0

1가지 숫자를 이용하여 3을 구하는 경우의 수 =  3

 

이 2가지 경우의 수를 더해주면 2가지 숫자를 이용하여 3을 구하는 경우의 수가 나오게 된다.

ex) 2+1, 1+2, 3+0, 0+3

 

 

 

 

 

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

 

 

점화식을 작성하기는 하였지만 어떤 연관관계가 있길래  2개의 값을 더해주면 정답이 나오는지 잘 이해가 가지 않는다.

이 부분은 조금 더 찾아보아야겠다.

---

코드

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k  =sc.nextInt();
        long[][] dp = new long[k+1][n+1];
        long mod = 1000000000;

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

}