[JAVA] 백준 2225번- 합분해

 

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

2225번: 합분해

 

 

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

public class Main{
    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());

        long[][] dp = new long[201][201];

        for(int i=0; i<=n; i++){
            for(int j=1; j<=k; j++){
                if(j==1 || i==0) dp[i][j] = 1;
                else dp[i][j] = dp[i-1][j] + dp[i][j-1] % 1000000000;
            }
        }

        System.out.println(dp[n][k] % 1000000000);
    }
}

 

 

dp[n][k] = n을 k개의 숫자(0~n)로 만드는 경우의 수 

 

 

이거는 노가다로 쓰면서 표를 그려보니 규칙을 발견해서 

 

dp[i][j] = dp[i-1][j] + dp[i][j-1]

이런 점화식을 세워서 풀었다. 

 

 

 

논리적으로 생각해보면 이렇다. 

 

 

 

예를 들어, n=4, k=3 라고 하자.

0~4까지의 숫자 중 3개의 합이 4가 되는 경우의 수를 구하는 것이다.

 

이것은 (2개의 숫자로 만든 합) + (0부터 4까지의 숫자 중 하나) 로 표현할 수 있다.  

 

0을 2개의 숫자로 만드는 경우의 수  (마지막에 4 더한 경우)

1을 2개의 숫자로 만드는 경우의 수 (마지막에 3 더한 경우)

2를 2개의 숫자로 만드는 경우의 수 (마지막에 2 더한 경우)

3을 2개의 숫자로 만드는 경우의 수 (마지막에 1 더한 경우)

4를 2개의 숫자로 만드는 경우의 수 (마지막에 0 더한 경우)

 

위의 모든 경우의수를 합한 것이 4를 3개의 숫자로 만드는 경우의 수가 된다. 

 

이를 점화식으로 표현한다면 이렇게 표현할 수 있다.

 

 

dp[n][k] = dp[0][k-1] + dp[1][k-1] + .... + dp[n][k-1]

 

 

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

public class Main{
    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());

        long[][] dp = new long[201][201];


        for(int i=0; i<=n; i++){
            dp[i][1] = 1;
        }

        for(int i=0; i<=n; i++){
            for(int j=1; j<=k; j++){
               for(int m=0; m<=i; m++){
                   dp[i][j] += dp[m][j-1] % 1000000000;
               }
            }
        }

        System.out.println(dp[n][k] % 1000000000);
    }
}

 

 

사실 dp[0][j-1]부터 dp[i-1][j-1]까지 모두 더한 값이 dp[i-1][j] 에 저장 되어 있기 때문에,

 

 

dp[i][j] = dp[i-1][j] + dp[i][j-1]

이렇게 처음 풀이로 푼 점화식이 도출될 수 있었던 것이다. 

이 방식이 시간 복잡도는 더 작다.

 

단순히 규칙만 찾는게 아니라 그 규칙이 어떻게 생겨난건지 더 깊이 생각해봐야할것 같다.