[백준/1413] 박스 안의 열쇠 (Python)

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

1413번: 박스 안의 열쇠

 

Difficulty : Platinum 5

 

Status : Solved

 

Time : 00:18:10

 

---

 

문제 설명

 

1부터 N까지 번호가 매겨진 박스와 1부터 N까지 번호가 매겨진 열쇠가 있다. i번째 키는 i번째 박스를 열 수 있다.

다못이는 각각의 박스에 정확하게 하나의 열쇠를 무작위로 넣는다. 각각의 열쇠가 박스에 들어갈 확률은 모두 같다고 가정한다. 그러고 나서 박스를 모두 잠근다. 다못이에게는 M개의 폭탄이 있다. 폭탄은 잠겨져 있는 박스를 파괴하는 역할을 한다. 이때 박스 안에 있는 열쇠는 부서지지 않는다. 다못이는 모든 열쇠를 얻고 싶다. 그래서 다음 전략을 사용하기로 했다.

우선 잠겨져 있는 박스 하나를 선택해서 폭탄으로 파괴하고 열쇠를 얻는다. 각각의 잠겨져 있는 박스가 선택될 확률은 모두 같다. 그 열쇠로 열 수 있는 박스가 있으면 열고, 그 박스 속의 열쇠로 열 수 있는 박스가 있으면 또 열고, 이를 열 박스가 더 이상 없을 때까지 반복한다. 그러고 나서 폭탄이 남았으면 그 폭탄을 이용해서 이 전략을 반복한다.

다못이가 모든 열쇠를 얻을 확률을 구하는 프로그램을 작성하시오.

 

입력 및 출력

 

입력

 

첫째 줄에 박스와 열쇠의 개수 N과 폭탄의 개수 M이 공백을 사이에 두고 주어진다. N은 20보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다.

 

출력

 

다못이가 모든 열쇠를 얻을 확률을 A/B 형태로 출력한다. A와 B는 최대공약수가 1인 자연수이다.

 

입력 예시

 

4 2

 

출력 예시

 

17/24

 

 

---

 

풀이

 

모든 열쇠 - 상자 경우의 수는 O(N!)가 된다. 오름차순으로 나열된 N개의 상자에 N개의 자연수를 매치시키는 경우의 수와 동일하다.

 

즉 직접 경우의 수를 제한하는 것보다, 위 상황에서 나타나는 구조적 특성을 이용할 필요가 있다.

 

상자에 들어있는 열쇠가 다음으로 접근할 상자를 나타내므로, 상자들을 이어 하나의 그래프로 나타내본다고 가정하자. 그러면 그 그래프는 하나 이상의 사이클을 그리는 그래프가 될 것이다. 그 사이클의 개수는 1개(모든 상자가 순환적으로 연결됨)에서 N개(모든 상자에 자기 자신을 열 수 있는 열쇠가 있음) 가 된다. 즉 N개의 상자 및 열쇠가 주어졌을 때, 사이클 개수에 대한 각각의 경우의 수를 구한다고 볼 수 있다. 모든 경우의 수는 (사이클의 경우의 수의 총합)이 될 것이고, 이 중 다못이가 모든 열쇠를 얻을 경우의 수는 (사이클의 수가 M개 이하인 경우의 수의 총합)이 된다.

 

또한, 우리는 i개의 상자에서 j개의 사이클이 발생하였을 때, i+1번째 상자 및 열쇠를 추가해볼 수 있을 것이다. 다음 두 가지 경우가 성립한다.

• i+1번째 상자가 i+1번째 열쇠를 가지고 있는 경우 : 사이클이 하나 더 추가되므로 i+1번째 상자에서 j+1개의 사이클이 발생하는 경우와 동일하다. 따라서 dp[i+1][j+1] += dp[i][j] 로 둘 수 있다.
• i+1번째 상자와 i+1번째 열쇠가 다른 장소에 있는 경우 : 이 경우는 사이클 내부에 하나의 노드를 더 삽입하는 경우와 동일하다. 이를테면, x -> y 구조가 존재할 때( 1 <= x <= i, 1 <= y <= i  ), 이 x와 y 사이에 하나의 노드를 삽입할 수 있다. 그렇다면 구조는 x -> (i+1) -> y가 되며, x상자에 i+1번째 열쇠가, i+1번째 상자에 y번째 열쇠가 있는 경우와 동일하다.
  이 경우 사이클은 j개로 동일하다. 전체 사이클에서 i+1번째 노드를 삽입할 수 있는 구조 역시 i개이므로, dp[i+1][j] += dp[i][j] * i 로 둘 수 있다.

즉 DP로 우리가 원하는 경우의 수들을 O(N^2)시간복잡도 내에 유도해낼 수 있다. 또한 마지막에 출력을 기약분수 형태로 나타내야하므로, 최대공약수를 구하여 나타내어주기만 하면 된다.

 

풀이 코드

N, M = map(int, input().split())

def gcd(a, b) :
  ta, tb = a, b
  while b :
    a, b = b, a % b
  return ta // a, tb // a

dp = [[0]*(N+1) for _ in range(N+1)]
dp[1][1] = 1

for i in range(1, N) :
  for j in range(1, i+1) :
    dp[i+1][j+1] += dp[i][j]
    dp[i+1][j] += dp[i][j] * i

tot_num = sum(dp[-1])
boom_num = sum(dp[-1][:M+1])
tot_num, boom_num = gcd(tot_num, boom_num)
print('{}/{}'.format(boom_num, tot_num))

풀이 완료!