알고리즘 풀이 - 백준 2225(합분해, DP)

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제 링크는 여기를 참조

 

문제의 내용을 보려면 아래 더보기 클릭

 

이 문제는 N, K가 주어질 때, N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제이다.

 

 

2. 풀이

 

0~N까지의 숫자가 K개 주어진다. 그렇다면 N=5, K=3이라고 한다면 0~5까지의 숫자가 3개 주어지고 3개의 합이 5가 된다는 의미이다. 

이를 구하려면 어떻게 해야 할까? 만약 마지막에 더할 숫자를 M이라고 가정해보자. 그렇다면 아래와 같을 것이다.

? + ? + M = 5

그렇다면, M이 만약 0이라면 이전 까지의 합이 5이고, 1이면 4, 2이면 3. 3이면 2, 4이면 1, 5이면 0이라는 의미이다. 즉 이를 식으로 쓰면 다음과 같다.

(5-M) + M = 5, 즉, 이전까지의 숫자의 합에 N이 될 수 있는 임의의 값을 더한 것과 마찬가지다.

그렇다면 5를 만드는 경우의 수는 다음과 같다! DP[K][N]은 N을 K개의 숫자로 만드는 경우의 수라고 가정하자.
점화식 : DP[K][N] = DP[K-1][0] + DP[K-1][1] + ... + DP[K-1][N]

위 점화식을 보면, K-1개의 수를 통해 0 ~ N까지 만드는 방법의 수를 모두 더하고 있다. 왜냐면 마지막에 어떤 수가 오든 단 1가지만 오게 되어 있으니 상단의 모든 경우의 수를 합하면 현재 N을 K개의 숫자로 만들 수 있기 때문이다.

 

위의 내용이 이해가 됐다면 아래의 표를 통해 좀 더 직관적으로 이해해보자.

K↓ / N →	0	1	2	3
1	DP[1][0] = 1	DP[1][1] = 1	DP[1][2] = 1	DP[1][3] = 1
2	DP[2][0] = 1	DP[2][1] = 2	DP[2][2] = 3	DP[2][3] = 4
3	DP[3][0] = 1	DP[3][1] = 3	DP[3][2] = 6	DP[3][3] = 10

 

위 표를 통해 몇 가지 사실을 알 수 있다.

① N = 0일 때, DP[N][K] = 1이다.
  → K개의 숫자를 더해 0을 만드는 방법은 1개 밖에 없다.

② K = 1일 때, DP[N][K] = 1이다.
  → 1개의 숫자를 더해 N을 만드는 방법은 1개 밖에 없다.

③ DP[N-1][K] + DP[N][K-1] = DP[N][K] 가 된다.
  → 직관적인 이해는 잘 안되는데, 규칙상 이것도 가능하다는 것을 알 수 있다! 위 점화식이 아닌 이것을 이용해서 풀면 더 빠른 속도로 풀 수 있다.(시간복잡도 : O(KN))

 

따라서, 위의 식에 따라 작은 문제들이 반복되어 겹치며, 해당 결과를 그대로 최적 결과로 활용 가능하여 DP의 두 가지 조건인 Overlapping Subproblems와 Optimal Substructure를 만족한다.

그럼 이미 상단에서 점화식을 만들었으니 문제의 정의를 세워보자.

정의 : DP[K][N] = K개의 0~N의 숫자를 더해 N을 만들 수 있는 경우의 수

 

K, N이 모두 State가 되므로 2차원의 배열에 저장해야 한다. 기저 상태는 어떨까? 점화식에 따라 아래와 같이 지정
기저 상태 : DP[0][0] = 1

또는 N이 0일 때나 K=1일 때, DP[N][K]를 1로 지정해도 된다. 어떻게 코딩하느냐에 따라 다르게 만들어도 된다.

 

DP[0][0] = 1로 해두면 DP[1][0], DP[2][0] 등 차례대로 1이 입력되며 진행될 것이다. 코드로 이해해보자.
이와 같이 해결 시 시간복잡도는 $O(KN^2)$이 된다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

1) Bottom-up 방식

import java.io.*;

public class Main {
    static long dp[][];
    static final long MOD = 1000000000;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String line[] = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int k = Integer.parseInt(line[1]);
        
        dp = new long[k+1][n+1];
        // 기저 상태 지정
        dp[0][0] = 1;
        
        for(int i=1; i <= k; i++){
             for(int j=0; j <= n; j++){
                 for(int m=0; m <= j; m++){
                     dp[i][j] += dp[i-1][j-m];
                     dp[i][j] %= MOD;
                 }
             }
        }
        
        bw.write(String.valueOf(dp[k][n]));
        br.close();
        bw.flush();
    }
}

 

2) Top-Down 방식

import java.io.*;

public class Main{
    static long[][] dp;
    static final long MOD = 1000000000;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        
        String line[] = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int k = Integer.parseInt(line[1]);
        
        dp = new long[k+1][n+1];
        
        topDown(k, n);
        
        bw.write(String.valueOf(dp[k][n]));
        br.close();
        bw.flush();
    }
    
    // Top-Down 방식
    public static long topDown(int k, int n){
        // 여기서 반환 조건식을 지정함
        // 값이 최소값이 아니거나 n=0이면 반환
        if(dp[k][n] > 0) return dp[k][n]; // 값이 있거나 n이 0이면 반환
        if(n == 0 || k == 1) return dp[k][n] = 1;
        
        // 재귀를 통해서 값을 구해온다.
        for(int m=n; m >= 0; m--){
            dp[k][n] += topDown(k-1, m);
            dp[k][n] %= MOD;
        }
        return dp[k][n];
    }
}

 

3. DP[N-1][K] + DP[N][K-1] = DP[N][K] 규칙을 이용하는 경우

import java.io.*;

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));
        
        String[] s = br.readLine().split(" ");
        int N = Integer.parseInt(s[0]);
        int K = Integer.parseInt(s[1]);

        int 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]) % 1000000000;
                }
            }
        }
        bw.write(String.valueOf(dp[N][K]));
        bw.flush();
        br.close();
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.