[Python3] 올바른 괄호

이 문제는 tryhelloworld 에 있던 문제인데, 문제 내용은 다음과 같다.

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

• N = 1일 경우는 () 의 1가지만 존재하므로 1을 리턴하면 됩니다.
• 3일 경우에는 ((())), (())(), ()(()), ()()(), (()()) 의 5가지가 존재하므로 5를 리턴하면 됩니다.

어찌보면 쉬운 문제인데, 생각 보다 접근하기 어렵다. 동적 프로그래밍을 써서 괄호안에 또 다른 괄호 케이스 까지 해주는 문제이기도 하다. 이와 같이 하지 않는 방법으론 재귀함수를 쓰는 것인데, 숫자가 커질수록 시간이 기하급수적으로 커지니 추천은 하지 않는다.

사실, 이 문제는 꼼수가 있다. 카탈란수를 이용하는 것이다. 카탈란수는 (0,0)에서 (n,n)까지 격자 점을 지나는 최단거리의 경로중 y=x를 넘지않는 경우의 수이다.

이 카탈란수를 오른쪽으로 한칸가는것은 괄호'('를 하나 추가하는 것 그리고 위로 한칸 가는 것은 ')'를 추가하는 것으로 생각해보자. 그러면 올바른 괄호찾기랑 같은 문제가 되어 쉽게 구할 수 있다. 카탈란수의 일반항은 다음과 같다.

따라서 그저 math 라이브러리에 factorial함수만 불러오면 간단히 끝난다.

from math import factorial

f=factorial    

def parenthesisCase(n):

    return f(2*n)//(f(n)*f(n)*(n+1))