(20) [C++, Java] 백준 No.2225 : 합분해

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-21-DP-문제-풀이4-4-백준-No2225-합분해?category=864321

 

# C++

#include <iostream>

using namespace std;

long long d[201][201];

int main()
{
    int n, k;
    cin >> n >> k;

    d[0][0] = 1;

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

    cout << d[k][n] << "\n";
}

# Java

import java.util.*;
import java.math.*;

public class Main {
    public static long mod = 1000000000L;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        long[][] d = new long[k+1][n+1];
        d[0][0] = 1;
        for (int i=1; i<=k; i++) {
            for (int j=0; j<=n; j++) {
                for (int l=0; l<=j; l++) {
                    d[i][j] += d[i-1][j-l];
                    d[i][j] %= mod;
                }
            }
        }
        System.out.println(d[k][n]);
    }
}