[backjoon_2225] 합분해 (Java)

문제링크

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

2225번: 합분해

문제설명

문제

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

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

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

제한사항

제한시간	메모리제한
2초	128MB

* 출처 : https://www.acmicpc.net/

문제풀이

위 문제는 DP를 사용하여 해결할 수 있다. 

D(n,k)를 n이라는 수를 k개의 수의 합으로 표현하는 방법의 총 개수라고 정의하여보자.

그리고 D(n,k)의 마지막에 올 수 있는 수를 고려해보면, 0~n임을 알 수 있다.

 

마지막에 오는 수를 고려했다는 것은 그 앞에 값을 표현하는 데 필요한 개수는 k-1개가 된다. 그리고 구하고자 하는 n의 값은 자연스럽게 n-고려한 값이 될 것이다. 따라서 우리가 생각한 마지막 수를 i라고 생각한다면, 우리는 다음과 같은 점화식을 구할 수 있다.

D(n,k) = D(n-i,k-1) + i (i = 0 ~ n)

위 식은 i를 0부터 n까지 모두 대입하여 더해주는 값이다. 여기서 순서를 고려하지 않아도 된다고 하여서 k를 곱하거나 하는 행위가 필요하지 않는지 물음이 가는 사람들이 있을 수 있는데, i가 0부터 n까지 이동하며 자연스럽게 이러한 부분이 처리가 된다.

 

long count = 0L;
for(int i = 0; i <= n; i++){
    count += dp(n-i,k-1);
    count %= mod;
}

 

위에서 설명한 점화식을 해결하기 위한 식은 다음과 같다. i를 0부터 n까지 돌려가며 합을 구해주면 쉽게 D(n,k)를 구해줄 수 있다.

 

if(n ==0 || k == 1)
    return 1;
if(dp[n][k] != 0)
    return dp[n][k];

여기서, 종료되는 조건을 고려해보면, n이 0이되는 경우(무조건 0이므로 1개), k가 1이 되는 경우(1개의 수로 표현할 수 있는 것이니 무조건 1)이 된다. 그리고 dp로 데이터를 사전에 계산했다면 처리해준다.

구현코드

import java.util.*;

public class Main {
    public static long mod = 1000000000L;
    static long[][] dp = new long[201][201];
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        long value = dp(n, k);
        System.out.println(value);

    }

    public static long dp(int n, int k){
        if(n ==0 || k == 1)
            return 1;
        if(dp[n][k] != 0)
            return dp[n][k];

        long count = 0L;
        for(int i = 0; i <= n; i++){
            count += dp(n-i,k-1);
            count %= mod;
        }

        dp[n][k] = count;
        return count;
    }
}

 

시간복잡도

해결해야할 문제의 수 : n*k

문제를 하나 처리하는 데 걸리는 시간 : n

최종 시간 복잡도 : O(k*n^2)