[Python 3] BOJ - 1413 "박스 안의 열쇠"

 # 문제 링크 : https://www.acmicpc.net/problem/1413

1413번: 박스 안의 열쇠

 # 풀이 :

 개인적으로 이 문제의 핵심은 제1종 스털링 수를 이해하는 것이다. 제1종 스털링 수에 대한 설명은 여기를 참고하면 된다. 그런데 사실 이 문제는 제1종 스털링 수를 모른다 해도 충분히 풀 수 있다.

<그림 1. N = 3일때 모든 경우의 수>

 그림 1은 상자가 3개일 때 가능한 6가지 경우의 수를 나타낸 것이다. 빨간색 글자들로 나타낸 조합은 폭탄이 3개가 있어야 모든 상자를 열 수 있는 조합이다. 파란색 글자들로 나타낸 조합은 폭탄이 2개가 있어야 모든 상자를 열 수 있는 조합이다. 초록색 글자로 나타낸 조합은 폭탄이 1개만 있어도 모든 상자를 열 수 있는 조합이다.

<그림 2. N = 2일 때 모든 경우의 수>

 그림 2는 상자가 2개일 때 가능한 2가지 경우이다. 그런데, 그림 1의 경우는 그림 2에서 파생이 가능하다. 아래의 그림을 보자

<그림 3. N = 2에서 N = 3 이행과정>

 그림3의 밑줄은 열쇠 3이 들어갈 수 있는 부분이다. 첫번째 경우의 첫번째 빈칸에 3을 넣게 되면 그림 1의 초록색 경우(3-1-2, 폭탄이 하나만 필요한 경우)에 해당한다. 첫번째 경우의 두번째 빈칸에 3을 넣게 되면 그림 1의 파란색 경우(1-3-2, 폭탄이 두개 필요한 경우)에 해당된다. 첫번째 경우의 세번째 빈칸에 3을 넣게 되면 그림 1의 빨간색 경우(1-2-3, 폭탄이 세개 필요한 경우)에 해당된다.

 두번째 경우의 첫번째 빈칸에 3을 넣게 되면 그림 1의 파란색 경우(3-2-1), 두번째 경우의 두번째 빈칸에 3을 넣게 되면 그림 1의 초록색의 경우(2-3-1), 두번째 경우의 세번째 빈칸에 3을 넣게 되면 파란색 경우(2-1-3)이 된다. 따라서, 이전의 경우로 부터 현재의 경우가 파생되므로 이 문제는 다이나믹 프로그래밍으로 풀 수 있다.

 D[i][j]를 상자가 1번 부터 i번까지 있을 때, 폭탄 j개를 사용할 때 전체 상자를 열 수 있는 경우의 수라고 정의하자. 그런데 위 그림3과 같이 i + 1번째 경우를 고려할 때, 맨 뒤 빈칸에 붙이면 상자의 순서가 그대로 유지되고, 맨 뒤에 붙였으니 마지막 상자는 항상 마지막 열쇠와 같게 되므로 필요한 폭탄의 수는 1씩 증가한다.

 그런데 마지막에 붙이는 경우가 아니라면 가능한 빈칸의 갯수는 i개이다. 따라서 마지막에 붙이는 경우가 아니고 폭탄의 수를 1개 추가하려면 붙이기 전의 경우의 수에 가능한 빈칸을 곱해주면 되므로 점화식은 아래와 같다

<그림 4. 점화식>

 

 # 코드

import sys, math

# 입력 및 d배열 생성
n, m = map(int, sys.stdin.readline().split())
d = [[0] * 21 for _ in range(21)]

# n = 1, m = 1인 경우는 갱신
d[1][1] = 1

# 점화식
# j가 1부터 i까지 순회하는 이유는 i번째 박스일 때 i + 1번째 열쇠가 존재할 수 없기 때문
for i in range(2, n + 1):
    for j in range(1, i + 1):
        d[i][j] = d[i - 1][j - 1] + (i - 1) * d[i - 1][j]

# bunza : 상자가 n개이고 폭탄이 m개 일때 가능한 모든 경우의 수
bunza = 0
for i in range(1, m + 1):
    bunza += d[n][i]

# bunmo : 상자가 n개일 때 모든 경우의 수
bunmo = 1
for i in range(1, n + 1):
    bunmo *= i

# 최대 공약수를 이용하여 기약분수 처리 후 정답 출력
print('%d/%d' % (bunza // math.gcd(bunza, bunmo), bunmo // math.gcd(bunza, bunmo)))