1413 : 박스 안의 열쇠

풀이

모든 열쇠를 얻으러면, 열쇠들 사이에 사이클이 생겨야한다.

우리에겐 k개의 폭탄이 있기 때문에, 이 열쇠들을 k개의 집합으로 나눠서 사이클을 만드는 경우의 수를 세면 된다.

n개의 원소를 k개의 원순열로 분할하기 위해, 제1종 스털링 수라는 걸 사용해보자.

s(n, k) = s(n-1, k-1) + (n-1)*s(n-1, k)라는 점화식이 나온다.

gcd로 최대공약수를 구하고, 합으로 나눠주면 끝!

코드

#include <stdio.h>
typedef long long ll;
int n, m, i, j;
ll dp[21][21] = { 1 }, div;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int main() {
	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; i++) for (j = 1; j <= i; j++)
		dp[i][j] = dp[i - 1][j - 1] + (i - 1)*dp[i - 1][j];
	for (i = 1; i <= n; i++) dp[n][i] += dp[n][i - 1];
	div = gcd(dp[n][n], dp[n][m]);
	printf("%lld/%lld", dp[n][m]/div, dp[n][n]/div);
	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-04-14 12:25

Read more posts by this author