합분해 : 2225번 - JAVA

---

1. 문제 링크

https://www.acmicpc.net/problem/2225

2225번: 합분해

 

 

---

2. 문제 설명

---

3. 문제 접근

-dp문제는 주로 규칙성을 찾고 점화식을 작성하는 것이 핵심이다!!

 

(1) 문제의 규칙성을 확인하기 위해 표를 작성해서 비교!

 

K ｜ N	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9
3	1	3	6	10	15	21	22	30	39
4	1	4	10	20	35	56	78	108	147

 

(2) 표에 표시한 값들의 규칙을 확인해보기

- K = 1일 때, 1을 리턴한다.

- N = 1일 때, 1을 리턴한다.

- ※규칙성 : (K,N) = (K-1, N) + (K, N-1) → (2,3) [하단 표에서 (2,2) + (3,1) 확인]

 

K ｜ N	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9
3	1	3	6	10	15	21	22	30	39

 

(3) 규칙성을 통해서 점화식 작성

dp[row][col] = dp[row-1][col] + dp[row][col-1];

 

 

---

4. 문제 풀이

package dp1;
 
import java.util.Scanner;
 
public class Dividing_Sum {
    static final long div = 1000000000;
    static int[][] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int k = sc.nextInt();
        dp = new int[k+1][n+1];
        
        for (int i = 1; i <= n; i++)    dp[1][i] = 1;
        for (int i = 1; i <= k; i++)    dp[i][0] = 1;
        
        for (int row = 1; row <= k; row++) {
            for (int col = 1; col <= n; col++) {
                dp[row][col] = (int) ((dp[row-1][col] + dp[row][col-1]) % div);
            }
        }
 
        System.out.println(dp[k][n]);
        
        sc.close();
    }
}
 

 

<정답 확인>

 

---

5. 느낀점 또는 특이사항

- bottom-up 방식으로 문제를 접근 -> top-down으로도 문제 풀이 접근해봐야겠다.