[알고리즘] 합분해 (백준 2225번)

2225번: 합분해

 다이나믹 프로그래밍 문제고 예전에 풀어본 적은 있으나 다 까먹었다... 근래에 DP 문제를 거의 안 풀어서 그런가 비교적 쉬운 난이도인데도 어떻게 풀어야할 지 한참 헤멘다...

 

Solution

1.  dp[N+1][K+1] 배열을 만든다. dp[i][j]는 i 수를 j개의 수로 이용해서 만들 수 있는 경우의 수다.
2. dp[i][0] = 0, dp[i][1] = 1이다. 즉 0개의 수를 이용해서 정수를 만들 수 있는 경우는 없고 1개의 수를 이용해서 정수를 만드는 경우는 자기자신 딱 하나 밖에 없다.
3. i = k + (i-k)라고 쳤을 때, [k][j-1] * [i-k][1] = [k][j-1]이다. ([i-k][1]은 어떤 경우에도 1이기 때문에)
4. dp[i][j]는 dp[i][j-1]의 경우의 수가 포함됨.

import javax.swing.text.Position;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Main {

    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static void solution() throws Exception
    {
        StringTokenizer strtok = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(strtok.nextToken());//0~N까지 정수
        int K = Integer.parseInt(strtok.nextToken());//사용 숫자 개수

        long dp[][] = new long[N+1][K+1];


        for(int i = 0;i <= N;i++)
        {
            //0개의 수로 i를 만드는 경우는 없다, 1개의 수로 i를 만드는 경우 i 자기 자신 뿐이다.
            dp[i][0] = 0;
            dp[i][1] = 1;

            for(int j = 2;j <= K;j++)
            {
                //k + (i - k) = i인데  j-1가지로 k를 만들고 i-k는 1가지 수로 만드는 경우이기에 [k][j-1] * [i-k][1] = [k][j-1]이다.
                //앞뒤순서가 다르면 다른 경우이므로 (순열) i까지 구한다.
                for(int k = 0;k <= i;k++)
                    dp[i][j] += dp[k][j - 1] % 1000000000;

                dp[i][j] %= 1000000000;
            }
        }

        bw.write((dp[N][K] % 1000000000)+"");


    }


    public static void main(String[] args) throws Exception {

        solution();
        bw.close();
        br.close();
    }
}