[Coderbyte] Bracket Combinations (Python)

 

문제

Bracket Combinations

HIDE QUESTION

Have the function BracketCombinations(num) read num which will be an integer greater than or equal to zero, and return the number of valid combinations that can be formed with num pairs of parentheses. For example, if the input is 3, then the possible combinations of 3 pairs of parenthesis, namely: ()()(), are ()()(), ()(()), (())(), ((())), and (()()). There are 5 total combinations when the input is 3, so your program should return 5.

 

풀이과정

본 유형은 카탈란 수열을 이용해야 한다고 한다.
카탈란수는 두 가지 서로 대응하는 경우가 있어야 하고, 각각의 경우에 해당하는 경우가 반드시 동수인 경우 사용할 수 있다. 

올바른 괄호의 경우의 수 문제, 산을 오르는 문제 등이 있다. 정확한 식의 증명의 이해가 어려워 점화식을 외워두는 것도 좋을 것 같다

$\frac{1}{n+1} \binom{2n}{n}$

https://brilliant.org/wiki/catalan-numbers/

Catalan Numbers | Brilliant Math & Science Wiki

 

Script

def BracketCombinations(num):
  answer = int(factorial(2*num) / (factorial(num+1)*factorial(num)))
  # code goes here
  return answer

def factorial(num):
  if num==1:
    return num
  else: 
    return num * factorial(num-1)

# keep this function call here 
print(BracketCombinations(input()))