#카탈란 수와 올바른 괄호 경우의 수 찾기

카카오 프로그래머스에 수록된 아래의 알고리즘 문제가 있다.

올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호를 이리저리 움직이며 올바른 괄호를 찾던 민호는 N개의 괄호쌍이 있을 때, 올바른 괄호를 만들 수 있는 경우의 수가 궁금해졌습니다. 괄호 쌍의 개수 N개가 주어졌을 때, 경우의 수를 반환하는 parenthesisCase 함수를 완성해 보세요. 예를 들어 - N = 1일 경우는 () 의 1가지만 존재하므로 1을 리턴하면 됩니다. - 3일 경우에는 ((())), (())(), ()(()), ()()(), (()()) 의 5가지가 존재하므로 5를 리턴하면 됩니다.

올바른 괄호의 경우의 수를 찾는 문제인데, 괄호 쌍이 5개일 때 경우의 수 찾다가 포기하고 결국 검색했다.

그러다 이 문제가 '카탈란 수'로 이루어져 있다는 것을 알게 되었다. 세상에... 참 별의 별 수가 다 있네 - _-;;; 

어쨌든 이 수에 대한 설명은 

카탈란 수(catalan number)

요기에 잘 나와 있다. 

요건 대각선이 만나지 않는 경의 수라고...

허참.. 정말 별 희한한 게 다 있다. 그저 신기할 따름이다.

아무튼, 카탈란 수를 구하기 위한 최종 공식은,

구하고자 하는 쌍이 n개이고, 총 경우의 수를 x라고 할 때,

이다. 

겁나 간단하다 진짜... - _-;;;

def binomial(bin, n, k):
   if n==k or k==0 : return 1
   elif bin[n][k] > 0 : return bin[n][k]
   else :
      bin[n][k] = binomial(bin, n-1, k) + binomial(bin, n-1, k-1)
      return bin[n][k]


def cataln(n) :
   bin = [[0 for col in range(2*n + 1)] for row in range(2*n + 1)]
   return binomial(bin, 2*n, n) - binomial(bin, 2*n, n+1)

print(cataln(5))

이 문제 해결하는 파이썬 코드다. 이것도 겁나 간단...

Top-Down 방식으로 풀었다. 이항계수 구하는 코드 말고는 뭐.. 딱히..