BOJ 2225 합분해 (DP, 조합론)

백준 BOJ 2225번 : 합분해

Solved.ac 난이도 : Gold V

알고리즘 분류 : DP, 조합론

 

0~N까지의 수 K개를 조합하여 N을 만들 수 있는 경우의 수를 구하는 문제입니다.

이 때 중요한 것은, 수의 순서가 바뀌면 다른 조합으로 고려하며 조합에 0이 들어갈 수 있다는 것입니다.

즉 수 2개로 1을 조합하는 경우의 수는 (0, 1)과 (1, 0)으로 총 2가지입니다.

 

DP로 풀어야 함은 쉽게 파악이 가능한데, 수의 중복 허용과 순서 고려 때문에 경우의 수를 구하기가 쉽지 않습니다.

따라서 상황을 다음과 같이 전환시켜 생각하면 좋습니다.

 

0 이상의 정수 K개를 조합하여 N을 만들기 → N개의 공을 K-1개의 막대로 경계지어 K개의 묶음으로 나누기

 

예시를 들면 다음과 같습니다.

 

 

위는 4개의 공을 4개의 막대로 나누어 5개의 묶음으로 나눈 하나의 경우입니다.

즉, N = 4, K = 5일 때 그 중 하나의 경우입니다.

막대 사이에 공이 없다면 0으로 생각할 수 있습니다.

위의 그림의 경우에는 4 = 1 + 2 + 0 + 1 + 0으로 분할한 것입니다.

 

우리는 0 이상의 정수로의 분할을 위와 같은 공과 막대로의 배열로 일대일 대응시켜 생각할 수 있습니다.

 

이것은 N개의 공과 K-1개의 막대의 배치이므로, N+K-1 C K-1로 생각할 수 있습니다.

따라서 그냥 Combination만 dp로 계산해서 출력해주면 쉽게 답을 얻을 수 있습니다.

 

 

#include<bits/stdc++.h>
#define MAX 401
#define MOD 1000000000
using namespace std;

int combination(int N, int K) {
    if(N < K) return 0;

    int dp[MAX][MAX] = {1};

    for(int i=1; i<=N; i++)
        for(int j=0; j<=i; j++)
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD;

    return dp[N][K];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, K; cin >> N >> K;

    cout << combination(N+K-1, K-1);
}

 

Combination을 계산할 때는 n C k = n-1 C k-1 + n-1 C k라는 점화식을 이용하여 쉽게 계산할 수 있습니다.

물론 이 때 0 C 0 = 1로 정의해주고 연쇄적으로 계산시켜주어야 합니다.

모듈로 계산도 빠뜨리면 안됩니다.