백준(BOJ) 2225 : 합분해 (JAVA)

문제링크 : https://www.acmicpc.net/problem/2225

2225번: 합분해

높은 정답률(현재 42%)에 비해 개인적으로 푸는데 고생을 좀 했던 문제이다. 총 2가지 풀이법을 소개할 것인데, 1. 내가 이 문제를 처음 푼 방법, 2. 인터넷에서 검색할 수 있는 일반적인(?) 방법이다.

 

N = 5, K = 3일 때를 직접 일일히 세어가면서 구한다고 생각해보자. 일단 2개로 먼저 쪼개보면, (5, 0), (4, 1), (3, 2), (2, 3), (1, 4), (0, 5)가 될 것이다. 여기서 한 번 더 나눠야 하는데, 이 때는 마지막 수를 다시 2개로 쪼갠다고 생각하면 된다. 그러면 (5, 0, 0), (4, 1, 0), (4, 0, 1), (3, 2, 0), (3, 1, 1), (3, 0, 2)... 이 식으로 될텐데 아래 그림을 보면 이해가 될 것이다.

여기서 내가 고려한 점은

1. K를 위와 같은 방식으로 계속 증가시키면서, 마지막 수의 개수를 카운트한다. (마지막 수만 경우의 수에 영향을 미치므로)

2. 마지막 수는 0 ~ N까지의 수인데, K가 증가할 때 임의의 i의 개수는 바로 직전 마지막 수들 중 i보다 큰 수들의 개수를 모두 더한 값이 된다. (위의 그림을 예로 들면, 3의 개수는 바로 직전의 3 ~ 5의 개수를 합친 것과 같다)

 

이를 고려하여 풀이한 소스는 아래와 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        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());
        
        int[] cnt = new int[n + 1];
        cnt[n] = 1;
        
        for(int i = 2; i <= k; i++) {
            int[] tmp = new int[n + 1];
            tmp[n] = 1;
            
            for(int j = n - 1; j >= 0; j--) {
                tmp[j] = tmp[j + 1] + cnt[j];
                tmp[j] %= 1_000_000_000;
            }
            
            cnt = tmp;
        }
        
        long sum = 0;
        
        for(int i = 0; i <= n; i++) {
            sum += cnt[i];
            sum %= 1_000_000_000;
        }
        
        System.out.println(sum);
    }
}

 

이번에는 인터넷에서 흔히 볼 수 있는 일반적인(?) 풀이법에 대한 설명이다.

 

N = 5, K = 3일 때를 구한다고 가정해보면, 

0 ~ 5의 수 중 3개를 선택하여 5를 만드는 경우의 수 = 첫번째 수를 0으로 선택하고, 0 ~ 5의 수 중 2개를 선택하여 5를 만드는 경우의 수 + 첫번째 수를 1으로 선택하고, 0 ~ 4의 수 중 2개를 선택하여 4를 만드는 경우의 수 .....

이런 식으로 될텐데, 수식화 해보면 아래와 같다.

 

(N=5, K=3) = (N=5, K=2) + (N=4, K=2) + (N=3, K=2) + (N=2, K=2) + (N=1, K=2) + (N=0, K=2)

 

여기서 우리는 규칙성을 확인할 수 있는데, 이를 다시 수식화 해보면 아래와 같다.

 

(N=i, K=j) = (N=i, K=j-1) + (N=i-1, K=j-1) + (N=i-2, K=j-1) + ..... + (N=0, K=j-1)

<-> (N=i, K=j) = (N=i, K=j-1) + (N=i-1, K=j)

 

위에서 얻어낸 점화식과 함께 아래사항을 초기값으로 이용하면 답을 도출해낼 수 있다.

1. K = 1 일 때 경우의 수는 1이다.

2. N = 1 일 때 경우의 수는 K이다.

 

코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        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());
        
        int[][] dp = new int[n + 1][k + 1];
        
        for(int i = 1; i <= k; i++) {
            dp[1][i] = i;
        }
        
        for(int i = 1; i <= n; i++) {
            dp[i][1] = 1;
        }
        
        for(int i = 2; i <= n; i++) {
            for(int j = 2; j <= k; j++) {
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1_000_000_000;
            }
        }
        
        System.out.println(dp[n][k]);
    }
}

 

두 코드 모두 동일한 시간복잡도를 가지고 있지만, 개인적으로 두 번째 풀이방법이 더 기억하기도, 이해하기도 쉬운 것 같다.