백준 1413번 박스 안의 열쇠 (Python 3)

 

Baekjoon online judge 1413번 파이썬

 

링크

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

1413번: 박스 안의 열쇠

소스코드

import sys
from collections import deque
input=sys.stdin.readline

def gcd(a, b):
  while (b != 0):
    temp = a % b
    a = b
    b = temp
  return abs(a)

def reduceFraction(bunja, bunmo):
  frac = [ bunja, bunmo ]

  if (frac[1] == 0): # 분모가 0일 경우에 에러 반환
    frac[0] = 0
    frac[1] = 0
    return frac

  gcd_result = gcd(frac[0], frac[1])

  frac[0] = str(frac[0] // gcd_result)
  frac[1] = str(frac[1] // gcd_result)

  return frac

n,m=map(int,input().split())

dp=[[0 for _ in range(21)] for _ in range(21)]
dp[1][1]=1

for i in range(1,n+1):
    for j in range(1,i+1):
        if i==1 and j==1:
            continue
        dp[i][j]=dp[i-1][j-1]+(i-1)*dp[i-1][j]


for i in range(1,n+1):
    dp[n][i]+=dp[n][i-1]

print('/'.join(reduceFraction(dp[n][m],dp[n][n])))