[99클럽 코테스터디 24일차 TIL / 백준] 2225 - 합분해 (DP)

99클럽 코테스터디 24일차 TIL
KeyWord : DP

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

---

 

풀이

N과 K의 크기를 1부터 증가시키며 메모제이션 하여 해결할 수 있다.

dp[k+1][n+1]라는 배열을 선언한 후, dp[i][j]에 각 경우의 수를 저장해가는 식으로 진행하자.

문제에서 주어진 예제입력 6 4를 기준으로 dp 배열을 시각적으로 나타내보았다.

K\N	0	1	2	3	4	5	6
1	1	1	1	1	1	1	1
2	1
3	1
4	1

일단 초기 dp가 이렇게 만들어진다는 것까지는 쉽게 이해된다. N=0일 때는 K가 얼마가 되든 K개의 0을 더하는 경우의 수 1, K=1일 때는 자기자신 하나만 포함하는 경우의 수 1이 된다.

이제 나머지 빈칸을 어떻게 채울지 고민해야 한다.

수가 너무 작으면 이해하기 힘드므로 dp[3][2] 일 때를 생각해보자.

• 0 + 0 + 2
• 0 + 2 + 0
• 2 + 0 + 0
• 0 + 1 + 1
• 1 + 0 + 1
• 1 + 1 + 0

일단 dp[3][2]는 이렇게 6개의 경우의 수가 나온다. 하지만 우리는 여기서 규칙성을 찾아야 한다.

• 2개의 수를 사용하여 0을 만드는 경우의 수는 1이다.
  • dp[2][0] = 1
  • 여기에 2만 더하면 0 + 2가 되므로 2가 만들어진다.
• 2개의 수를 사용하여 1을 만드는 경우의 수는 2이다.
  • dp[2][1] = 2 → 0 + 1 / 0 + 1
  • 여기에 1을 더하면 1 + 1이 되므로 2가 만들어 진다.
• 2개의 수를 사용하여 2를 만드는 경우의 수는 2이다.
  • dp[2][2] = 3 → 0 + 2 / 1 + 1 / 2 + 0
  • 여기에 0을 더하면 2 + 0이 되므로 2가 만들어진다.

이렇게 만들어지는 모든 경우의 수를 더하면 6이 도출된다.

즉, dp[3][2] = dp[2][0] + dp[2][1] + dp[2][2] 이런 수식이 도출된다.

이 규칙성에 따라 식을 일반화 하면, dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j]이 된다.

이제 이 식을 이용하여 dp 배열을 채워보자.

K\N	0	1	2	3	4	5	6
1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7
3	1	3	6	10	15	21	28
4	1	4	10	20	35	56	84

해를 구했다. 당연히 dp[4][6]에 저장된 84가 문제의 해다.

 

이렇게만 해도 코드를 구현할 수는 있겠지만, 뭔가 계산량을 더 줄일 수 있을 것 같다. 이 상태로 구현을 한다면 3중 반복문을 사용해야 한다. 2중 반복만 되어도 불편한데, 3중이라니?

조금 더 규칙성을 찾아보자.

dp[3][2] = dp[2][0] + dp[2][1] + dp[2][2]

이 수식을 자세히 살펴보면, dp[2][0] + dp[2][1] = dp[3][1] 이라는 사실을 알 수 있다.

식을 더 정리하면, dp[3][2] = dp[3][1] + dp[2][2]이다. 이를 일반화 하면, dp[i][j] = dp[i-1][j] + dp[i][j-1]이 된다.

이제 진짜 코드로 구현하자.

 

코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Arrays;  
import java.util.StringTokenizer;  

public class Main {  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer stk = new StringTokenizer(br.readLine());  

        int n = Integer.parseInt(stk.nextToken());  
        int k = Integer.parseInt(stk.nextToken());  

        int[][] dp = new int[k + 1][n+1];  
        Arrays.fill(dp[1], 1);  
        for (int i = 0; i < k + 1; i++) {  
            dp[i][0] = 1;  
        }  

        for (int i = 1; i <= k; i++) {  
            for (int j = 1; j <= n; j++) {  
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000000;  
            }  
        }  

        System.out.println(dp[k][n]);  
    }  
}