백준 2225번 - 합분해 (Java)

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

2225번: 합분해

코드 :

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

public class Main {
    public static final int MOD = 1_000_000_000;
    static long[][] memo;
    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());

        memo = new long[N+1][K+1];
        System.out.println(dp(N, K));

    }
    public static long dp(int N, int K){
        if(memo[N][K] == 0){
            if(K == 1){
                return 1;
            }
            long count = 0;
            for (int i = 0; i <= N; i++) {
                count += dp(N - i, K - 1);
            }
            memo[N][K] = count % MOD;
        }

        return memo[N][K];
    }
}

어떻게 풀었는지 기억이 안난다. 내일 다시 정리해야겠다.