백준1413 박스 안의 열쇠

작성일 | In

문제 링크

  • http://icpc.me/1413

사용 알고리즘

  • DP

시간복잡도

  • O(N2)

풀이


위 사진처럼 1번 박스에는 2번 열쇠, 2번 박스에는 3번 열쇠, 3번 박스에는 4번 열쇠, 4번 박스에는 1번 열쇠, … 처럼 있다고 합시다.
아래 사진처럼 그래프로 나타내보면, 폭탄 하나를 사용해 사이클에 있는 모든 박스를 열 수 있다는 것을 알 수 있습니다.

위 그래프에서 8번 박스가 새로 들어온다고 생각해봅시다.
8번 박스가 들어오는 방법은 기존 사이클에 들어가거나, 혼자서 새로운 사이클을 구성하거나, 총 2가지입니다.

기존 사이클에 들어가는 것은 간선 중간에 들어가는 것이라고 볼 수 있습니다. N번째 박스가 새로 들어갈 때, N-1개의 간선 중 하나를 선택해 들어갈 수 있습니다.
혼자 새로운 사이클을 만드는 것은 폭탄이 하나 더 필요하다는 것을 의미합니다.

dp[n][m] = n개의 열쇠를 정확히 m개의 폭탄을 이용해 모두 얻는 경우의 수
라고 정의를 한다면,
dp[n][m] = (i-1) * dp[i-1][j] + dp[i-1][j-1] 이 됩니다.

모든 열쇠를 얻을 확률을 구해야 하므로 (1 ~ m)개의 폭탄을 사용해서 얻는 경우의 수를 (1 ~ n)개의 폭탄을 사용해서 얻는 경우의 수로 나누어주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b){
	return b ? gcd(b, a%b) : a;
}

ll dp[22][22];

int main(){
	int n, m; cin >> n >> m;
	dp[1][1] = 1;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= i; j++){
			if (i == 1 && j == 1) continue;
			dp[i][j] = dp[i - 1][j - 1] + (i - 1) * dp[i - 1][j]; //새로운 사이클에 끼는 경우 + 기존 사이클에 끼는 경우
		}
	}

	for (int i = 1; i <= n; i++) dp[n][i] += dp[n][i - 1];
	ll g = gcd(dp[n][m], dp[n][n]);
	cout << dp[n][m] / g << "/" << dp[n][n] / g;
}