[백준] 2225번 - 합분해

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

2225번: 합분해

---

DP문제...

dp[k][n]에 정수 k개로 n을 만드는 경우의 수를 저장해야 한다는 것까지는 생각했는데

역시나 점화식을 찾지 못했다...

뭔가 느는 것 같으면서도 아직도 아리송한 DP...ㅠㅠ

 

---

[문제 풀이]

 

dp[k][n]에 1~n까지의 정수 k개로 n을 만드는 경우의 수를 저장하면 된다

그럼 dp[k][n]을 만들기 위해 다음과 같은 경우의 수가 나올 수 있다

 

dp[k][n]

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

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

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

= ....

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

 

위에서 뒤의 숫자들은 진짜 숫자이다

암튼 위와 같이 되니까 최종 점화식은 다음과 같다

 

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

 

위의 식을 점화식을 통해 k와 n에 대해서 모두 적용해주면 된다!

 

 

 

자바 코드)

import java.util.Scanner;

public class boj2225 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        // dp[k][n] : k개의 정수로 n을 만드는 경우의 수
        int[][] dp = new int[k+1][n+1];

        // 1개로 n을 만드는 경우의 수는 무조건 1개이다
        for(int i=0;i<=n;i++) {
            dp[1][i] = 1;
        }

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

---

참고)

https://ws-pace.tistory.com/61

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