백준 2225번: 합분해

문제

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

2225번: 합분해

---

풀이

0부터 n까지의 정수 k개를 더해서 그 합이 n이 되는 경우의 수를 구하는 문제입니다.

이때 덧셈의 순서가 바뀐 경우는 다른 경우(1+2와 2+1은 서로 다른 경우)이며 한 개의 수를 여러 번 쓸 수도 있습니다.

---

코드

자바

탑다운 방식을 이용한 코드입니다.

dp 배열은 임의의 수 x, y가 있을 때 x를 만들어야 할 때 더할 수 있는 남은 횟수가 y인 경우의 수를 의미합니다.

decomposition 함수에서 y가 1이라면 x를 수 1개를 이용하여 만들 수 있는 경우는 x 1가지 이므로 1을 반환하고 y가 1이 아니고 dp[x][y]가 0이라면 i를 포함한 for문 안으로 들어갑니다. 이때 i는 어떤 수를 더했을 때 n을 만들기 위해 남은 숫자를 의미하기 때문에 i는 x부터 0까지 돌아갑니다. dp[x][y]에 decomposition(i, y - 1)를 더해주고 문제 조건에 맞춰 1,000,000,000으로 나눈 나머지를 dp[x][y]에 넣어줍니다. for문이 끝나면 dp[x][y]를 반환합니다.

모든 입력이 끝나면 decomposition(n, k)을 실행하여 dp[n][k] 값을 받아 출력합니다.

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

public class Main {

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

    public static int decomposition(int x, int y) {
        if (y == 1) {
            return 1;
        } else if (dp[x][y] == 0) {
            for (int i = x; i >= 0; i--) {
                dp[x][y] += decomposition(i, y - 1);
                dp[x][y] %= mod;
            }
        }
        return dp[x][y];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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];
        System.out.println(decomposition(n, k));
    }
}

C언어

바텀업 방식을 이용한 코드입니다.

dp 배열은 탑다운 방식의 코드에서의 의미와 동일합니다. 임의의 수 x를 1개의 숫자로 만들 수 있는 경우의 수는 1개이며 1을 임의의 수 y개의 숫자로 만들 수 있는 경우의 수는 0과 1을 조합하여 y개이기 때문에 dp[x][1] 값은 1이고 dp[1][y] 값은 y입니다.

또한 n을 k개의 숫자로 만들 수 있는 경우의 수를 점화식으로 표현한다면 dp[n][k] = dp[0][k - 1] + dp[1][k - 1] + … + dp[n][k - 1]이고 이는 dp[n - 1][k] + dp[n][k - 1] = dp[0][k - 1] + dp[1][k - 1] + ... + dp[n - 1][k - 1] + dp[n][k - 1]으로 볼 수 있습니다.

따라서 i와 j를 포함한 이중 for문에서 dp[i - 1][j] + dp[i][j - 1]을 1,000,000,000으로 나눈 나머지를 dp[x][y]에 넣어줍니다.

모든 입력이 끝나면 dp[x][y] 값을 출력합니다.

#include <stdio.h>
#include <stdlib.h>
const int mod = 1000000000;
main() {
	int n, k;
	scanf("%d %d", &n, &k);
	int** dp = (int**)malloc(sizeof(int*) * (n + 1));
	for (int x = 0; x <= n; x++) {
		dp[x] = (int*)malloc(sizeof(int) * (k + 1));
		dp[x][1] = 1;
	}
	for (int y = 0; y <= k; y++) {
		dp[1][y] = y;
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 2; j <= k; j++) {
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
		}
	}
	printf("%d", dp[n][k]);
}

 

---

결론

바텀업 방식을 이용한 코드에서 해당 점화식을 찾는 것이 어려웠던 문제였습니다. 이렇게 계속 연습을 해도 탑다운 방식을 이용한 코드가 재귀를 이용하기 때문에 저에게 더 쉽게 느껴지는 것 같습니다.