백준 1413 - 박스 안의 열쇠

www.acmicpc.net/problem/1413

 

문제의 상황을 상상해보자.

 

박스에 열쇠를 넣다 보면 열쇠로 다른 박스를 여는 상황이 마치 방향 그래프를 구성하는 것처럼 보임을 알 수 있다.

 

5번 박스에 5번 열쇠가 있다면 이는 루프를 가진 그래프가 되는 것이다.

 

박스와 열쇠의 관계는 여러개의 사이클 그래프가(루프 포함) 나오는 것으로 생각할 수 있고, 이는 제1종 스털링 수로 환원된다.

 

제1종 스털링 수는 말 그대로 n개의 노드에서 m개의 사이클이 형성되는 경우를 나타내는 수열이다.

 

제1종 스털링 수의 점화식은 다음과 같다.

 

$s(n, k) = (n - 1)s(n - 1, k) + s(n - 1, k - 1) \; (s(0, 0) = 1)$

 

한 사이클을 순회하기 위해선 한 개의 폭탄이 필요함을 알 수 있으므로 폭탄을 m개 가지고 있으면 n개의 노드가 m개의 사이클을 가지는 경우까지 처리할 수 있다는 뜻이 된다.

 

따라서 주어진 조건에서 상자를 모두 여는 경우의 수는 $\sum_{i = 1}^{m}s(n, i)$이고 n개의 노드들에 대해 사이클이 생성되는 경우의 수는 $\sum_{i = 1}^{n}s(n, i)$이다.

 

두 수를 모두 구하고 최대공약수로 나눈 값을 출력해주면 된다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
using ll = unsigned long long;
 
int n, m;
ll dp[21][21];
 
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
 
    cin >> n >> m;
 
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j)
            dp[i][j] = (i - 1) * dp[i - 1][j] + dp[i - 1][j - 1];
 
    ll dominator = 0, numerator = 0;
 
    for (int i = 1; i <= n; ++i)
    {
        dominator += dp[n][i];
        if (i <= m)
            numerator += dp[n][i];
    }
 
    ll dv = gcd(dominator, numerator);
    cout << numerator / dv << "/" << dominator / dv;
}