[ 백준 2225번 ] 합분해

1. 문제

 

2225번: 합분해

 

2. 풀이

2차원 DP형태의 문제라 직관적으로 해답을 떠올리기 다소 어려운 유형의 문제라고 할 수 있다. 따라서 점화식을 먼저 한 번 도출해보도록 하자.

 

숫자 N을 정수 K개의 조합으로 만들 수 있는 문제를 다시 재조합하면 아래와 같이 생각할 수도 있다. dp[N][K]는 N을 K개 조합으로 만드는 경우의 수를 의미하고, 예시로 N = 6이고 K = 4라고 가정해보자.

 

(_ , _ , _ , L) 네 개의 숫자 조합에서 마지막 자리를 L(0 ≤ L ≤ 6) 로 결정한다면, L 값에 따라서 아래 표의 경우의 수가 만들어짐을 알 수 있다.

 

L	case
0	dp[6][3]
1	dp[5][3]
2	dp[4][3]
3	dp[3][3]
4	dp[2][3]
5	dp[1][3]
6	dp[0][3]

 

표는 마지막 자리 수 L을 N에서 뺀 값(N - L)을 (K - 1)개의 숫자를 이용해서 만드는 방식을 의미한다. 마지막 자리인 L이 모두 서로 다른 숫자여서 모든 경우의 수가 서로 다른 경우의 수를 만들고 있음이 보장된다. 따라서 점화식은 아래와 같이 정리할 수 있다. 다만, 주의해야 할 점은 dp[N][1]은 항상 1이라는 것과 dp[1][K] 는 항상 K라는 점이다. 왜냐하면 당연하게도 N을 한 개의 숫자로 만드는 방법은 N만 배치하는 것이므로 한 가지 경우 밖에 없으며, 1을 K개의 숫자로 만드는 것은 비트처럼 K 개의 자리에서 1을 배치하는 경우의 수이기 때문이다.

 

dp[N][K] = dp[0][K - 1] + dp[1][K - 1]  + ... + dp[N][K - 1]

 

해당 점화식을 기반으로 해서 풀이하면 쉽게 풀 수 있지만, 점화식의 결과로 만들어진 dp 배열에는 재미있는 규칙이 숨어있다.

 

N↓ / K→	1	2	3	4
1	1	2	3	4
2	1	3	6	10
3	1	4	10	20

 

바로 dp[N][K] = dp[N - 1][K] + dp[N][K - 1] 이라는 규칙이다. 이는 누적합과도 관련있는 내용인데, 왜 이것이 성립하는지를 한 번 각자 알아보쟈🤗

 

3. 소스코드

public class Main {

    static final int MOD = 1000000000;
    static int[][] dp;

    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());

        dp = new int[N + 1][K + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                if (j == 1) {
                    dp[i][j] = 1;
                } else if (i == 1) {
                    dp[i][j] = j;
                } else {
                    dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
                }
            }
        }

        bw.write(dp[N][K] + "");
        bw.close();
        br.close();
    }
}

GitHub - kwanik-kor/BOJ: Baekjoon Online Judge - explanation of solved problems and complete code