백준 2225 합분해 / python

문제 : 2225

풀이 point

dp를 활용하여 문제를 풀 수 있다.

dp[n][k]를 통해 N이 얼마일 때 K개로 만들 수 있는 조합을 구한다.

주의) 0을 포함한다는 문구가 가장 중요하다.

N을 만들기 위해서 K-1개 조합 + N-1을 만들기 위한 K개 조합을 통해 우리가 구하려는 N일때 K개로 만들 수 있는 조합의 개수를 구할 수 있다.

풀이 방법

상향식 or 하향식을 통해 풀 수 있다. 점화식까지 구했으니 어떤 방법을 사용하여도 좋다. 다만 상향식이 한눈에 이해하기에는 더 편함이 있다.

값이 너무 커질 수 있으니 문제에 나와있는 MOD값으로 나누어주어야한다.

하향식

def recur(n, k):
    if k == 0: return 0
    if k == 1: return 1

    if dp[n][k]: return dp[n][k]

    res = 0
    for i in range(n+1):
        res += recur(i, k-1)%1000000000
    dp[n][k] = res%1000000000

    return dp[n][k]

N, K = map(int, input().split())

dp = [[0 for _ in range(K+1)] for _ in range(N+1)]

print(recur(N, K))

상향식(C++)

//백준 2225, 합분해
#include <iostream>

int dp[205][205]; //dp[N][K] N이 얼마일 때 K개로 만들 수 있는 조합

int main(){

    int N, K;
    std::cin >> N >> K;

    // dp[1][1] = 1; dp[1][2] = 2; dp[1][3] = 3; dp[1][4] = 4;
    // dp[2][1] = 1; dp[2][2] = 3; dp[2][3] = 6;

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

    for(int i{2}; i<=N; ++i){
        for(int j{1}; j<=K; ++j){
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1'000'000'000;
        }
    }

    std::cout << dp[N][K];

    return 0;
}