[백준 2225, Java] 합분해

문제

www.acmicpc.net/problem/2225

2225번: 합분해

 

풀이

0부터 n개의 수 k개를 더해서 n을 만든다고 할때 맨 마지막에 더하는 수를 생각해보자. 그 마지막 수에 올 수 있는 수는 0~ n이다. 마지막 수 앞에 오는 수는 0~ (n-마지막수) 중 k-1 개를 더해서 만든 수다.  

따라서  f(n,k) 를 0부터 n까지의 수 k개를 더해서 n을 만들 수 있는 경우의 수라고 하면 f(n,k) = f(n-m,k-1) (0<= m <=n)이다. 

 

check

• 점화식을 세울 수 있는 데까지는 할 수 있는데, 이를 구현하는데 시간이 걸린다.

• 처음에는 top-down으로 풀었는데, 이렇게 풀게되면 모든 경우에 대해서 한번의 호출이 일어나기 때문에 시간복잡도가 n의 k 제곱이되서 시간초과가 난다. 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int K;
    public static long[][] sqaure;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        sqaure = new long[N+1][K+1];

        long result = getNK2();
        bw.write(String.valueOf(result));
        bw.flush();

        br.close();
        bw.close();

    }
    public static long getNK(int n, int k){
        if(k==1){
            sqaure[n][k] =1;
            return 1;
        }
        else if(sqaure[n][k]!=0){
            return sqaure[n][k];
        }
        else{
            long sum = 0;
            for(int num = 0; num<=n; num++){
                sum+= getNK(num,k-1);
            }
            return sum;
        }
    }

    public static long getNK2(){
        sqaure[0][0] = 1;
        for(int n = 0; n<=N; n++){
            for(int k = 1; k<=K; k++){
                for(int m = 0; m<=n; m++){
                    sqaure[n][k] += sqaure[n-m][k-1];
                }
                sqaure[n][k] %=1000000000;
            }
        }

        return sqaure[N][K];
    }
}