[백준 1413] 박스 안의 열쇠

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

1413번: 박스 안의 열쇠

 

풀이를 봤더니 제 1종 스털링 수? 그게 머죠.. 아무튼 그런건 잘 모르겠고

다른 풀이들을 보니 확률을 구할 때 (상자를 여는 경우의 수)/(전체 경우의 수) 를 하는 방법을 많이 사용했지만

난 처음부터 분수를 사용했다.

 

파이썬에는 분수를 지원하는 짱짱 라이브러리가 있기 때문이다.

from fractions import Fraction

---

 

그래서 점화식도 그냥 $0 \sim 1$ 사이 확률로 나오게 할 것이다.

함수 $f(x: 상자 개수, \, y: 폭탄 개수)$ 를 한번 정의해 보자.

 

우선 예외 처리부터..

우선 상자가 $0$개 일때, $f(0, \, y)=1$ 이라는 것은 자명하다. (열 상자가 없으니 무조건 성공)

상자가 있으면서 폭탄이 없을 때, $f(x, 0)=0$ 이라는 것은 자명하다. (단 $x>0$)

 

나머지 경우에, 폭탄을 사용해야 하는데, 폭탄 $1$개로 상자를 몇 개 까지 열 수 있는가를 계산하는 것이 관건이다.

 

폭탄을 $1$개 써서 상자를 $1$개 열 확률:

$\displaystyle \frac1x$ (자기 자신의 번호가 들어있을 확률)

 

폭탄을 $1$개 써서 상자를 $2$개 열 확률:

$\displaystyle \frac{x-1}x \cdot \frac1{x-1}=\frac1x$

 

폭탄을 $1$개 써서 상자를 $3$개 열 확률:

$\displaystyle \frac{x-1}x \cdot \frac{x-2}{x-1} \cdot \frac1{x-2}=\frac1x$

---

 

폭탄을 $1$개 써서 상자를 $x$개 열 확률:

$\displaystyle \frac{x-1}x \cdot \frac{x-2}{x-1} \cdot \cdot \cdot \frac23 \cdot \frac12=\frac1x$

 

전부 $\displaystyle \frac1x$로 균등하다는 것을 알 수 있다.

따라서 $f(x, \, y)$는 다음과 같이 정의 가능하다.

 

$f\left( x,y\right) \begin{cases}1\left( x=0\right) \\ 0\left( x >0,y=0\right) \\ \dfrac{1}{x}\displaystyle\sum ^{x}_{k=1}f\left( x-k,y-1\right)\end{cases}$

 

그리고 상자의 수 $n$, 폭탄의 수 $m$이 주어지므로

$f(n, m)$을 구하면 된다.

 

$x\leq y$ 일때 $1$이다 라는 조건을 추가하면 약간의 최적화를 더 할 수 있다.

(상자보다 폭탄이 많으면 무조건 성공하기 때문)