CEO

문제 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net 문제 풀이 괄호의 문자열이 주어질 때, 올바른 괄호인지 찾는 문제이다. 이 문제는 `DP`로도 풀 수 있지만, 카탈랑 수로도 풀 수 있다. 카탈랑 수는 이진트리의 수를 셀 때 사용하는 수열이다. 카탈랑 수를 파이썬 코드로 나타내면 `factorial(2 * num) // (factorial(num) * factorial(num + 1))`이다. 이를 통해 문제를 해결할 수 있다. 코드 from math import factorial from sys impo..