[BOJ] 1413번: 박스 안의 열쇠

https://www.acmicpc.net/problem/1413

일단 열쇠가 랜덤으로 배치되므로 박스를 선택하는 순서는 고정을 해도 확률에 아무런 영향을 주지 않습니다. 편의를 위해 그냥 현재까지 열리지 않은 박스 중에 가장 번호가 작은 박스만 계속 선택한다고 합시다. D[N][K]를 N!가지의 박스 내의 열쇠 배열 순서중에 K개의 폭탄으로 박스를 모두 열 수 있는 경우의 수라고 할 때, 1번을 골라서 생기는 cycle의 길이를 생각해봅시다.

cycle의 길이가 1인 가지수는 박스 1 내에 열쇠 1이 들어있으면 되므로 (N-1)!

cycle의 길이가 2인 가지수는 박스 1 내에 열쇠 k(!= 1)이 들어있고, 박스 k 내에 열쇠 1이 들어있으면 되므로 (N-1)!

.

.

으로 전부 (N-1)! 가지임을 알 수 있습니다.

그렇기에 D[N][K] = D[N-1][K-1] + (N-1) * D[N-2][K-1] + (N-1)(N-2) * D[N-3][K-1] + ... 으로 답을 구할 수 있습니다. N이 작아 대충 짜도 전부 시간 내에 잘 동작하지만 factorial을 미리 계산해둘 경우 조금 더 편하게 식을 만들어낼 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/1413.cpp