[백준] 2225 합분해 - Dynamic Programming / Java

• 문제 링크

2225번: 합분해

 

• 풀이 과정

dp 배열을 2차원 배열로 생성하고, dp[n + 1][k + 1] 으로 크기를 지정한다.

 

이때 n = 1 일 때 i 개로 n을 만드려면 각각 i 개의 경우의 수가 존재,(dp[1][i] = i)

i 를 k = 1 개로 만드려면 각각 1개의 경우의 수가 존재하므로 해당 값들을 초기화시킨다.(dp[i][1] = 1)

 

이어서 규칙성을 찾기 위해 n = 1 ~ 3, k = 1 ~ 3 범위의 예시는 아래와 같다.

 

• dp[1][1] : 1 (1)
• dp[1][2] : 2 (1 + 0, 0 + 1)
• dp[1][3] : 3 (1 + 0 + 0, 0 + 1 + 0, 0 + 0 + 1)

 

• dp[2][1] : 1 (2)
• dp[2][2] : 3 (2 + 0, 0 + 2, 1 + 1)
• dp[2][3] : 6 (2 + 0 + 0, 0 + 2 + 0, 0 + 0 + 2, 1 + 1 + 0, 0 + 1 + 1, 1 + 0 + 1)

 

• dp[3][1] : 1 (3)
• dp[3][2] : 4 (3 + 0, 0 + 3, 2 + 1, 1 + 2)
• dp[3][3] : 10 (3+0+0, 0+3+0, 0+0+3, 2+1+0, 0+2+1, 1+2+0, 0+1+2, 2+0+1, 1+0+2, 1+1+1)

위에서 구한 경우의 수와 미리 초기화한 경우의 수까지 표현하면 아래와 같다.

n / k	0	1	2	3
0	0	1	1	1
1	0	1	2	3
2	0	1	3	6
3	0	1	4	10

위처럼 어떠한 경우의 수 dp[3][3] = 10 을 구하기 위해선

dp[3][2] + dp[2][3] = 4 + 6 을 수행해야 하는 규칙성을 찾을 수 있으며

이는 dp[i][j] = dp[i][j - 1] + dp[i - 1][j] 로 나타낼 수 있다.

 

반복문을 통해 dp[2][2] ~ dp[n][k] 까지 경우의 수를 구해 나가며 각각의 값에 % 1000,000,000 을 수행한다.

이 후 구하고자 하는 dp[n][k] 을 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[][] dp = new int[n + 1][k + 1];

        for (int i = 1; i <= k; i++)
            dp[1][i] = i;

        for (int i = 1; i <= n; i++)
            dp[i][1] = 1;

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

        bw.write(dp[n][k] + "\n");
        bw.flush();
    }

}