2225 - 합분해

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

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

해당 경우의 수를 1,000,000,000로 나눈 나머지를 출력하시오.

문제설명 정수 K개를 더해서 N을 만들어야 한다. d[K][N] -> "K개의 정수를 이용해 N을 만들었다" 라고 생각하자.

점화식을 구하기 위해 이전 항을 생각해보면, 정수 한 개를 빼야 하므로 d[K - 1]\[N - ?]와 같이 나타낼 수 있다. ?는 여러가지 경우가 있기 때문에 답을 구하기 전에는 알 수 없는 값으로, 이러한 수들을 반복문을 이용해 찾아주어야 한다.

따라서 d[K][N] = sum(d[K - 1]\[0 ~ N])과 같은 식을 가지고 구현을하면 된다.

 

위와 같이 식이 나온 이유는, K - 1번째 항의 값을 예측 할 수가 없기 때문이다. (ex : N이 5이고 K가 2라고하면 5는 0 + 5, 1 + 4, 2 + 3, 3 + 2, 4 + 1, 5 + 0 과 같은 경우들이 있다. 이 때 K - 1번째 항의 값은 계속해서 변하게 된다.)

점화식을 이용하기 위해 d[1][0 ~ N]값들을 모두 1로 초기화해 주었다.(한자릿수를 만들기 위해서는 무조건 수 한 개만 사용하기 때문.) 반복문이 3개인 이유는 K, N과 함께 Ln도 0부터 N까지 반복하며 개수를 세줘야 하기 때문이다. d[K - 1]\[0 ~ N] <- 0 ~ N 부분이 Ln으로 대체.

package backjoon;
import java.io.*;

public class Sum_of_Disassemble {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        int N = Integer.parseInt(inputs[0]);
        int K = Integer.parseInt(inputs[1]);
        int[][] d = new int[K + 1][N + 1];
        for (int i = 0;i <= N;i++) d[1][i] = 1; // d[1] 모든 항 1로 초기화
        for (int i = 2;i <= K;i++){ // K
            for (int j = 0;j <= N;j++) { // N
                for (int x = 0;x <= j;x++){ // Ln
                    d[i][j] += d[i - 1][j - x];
                    d[i][j] %= 1000000000;
                }
            }
        }d
        System.out.println(d[K][N]);
    }
}