백준: 10422 괄호

문제

10422번: 괄호

 

문제 풀이

 괄호의 문자열이 주어질 때, 올바른 괄호인지 찾는 문제이다. 이 문제는 `DP`로도 풀 수 있지만, 카탈랑 수로도 풀 수 있다. 카탈랑 수는 이진트리의 수를 셀 때 사용하는 수열이다. 카탈랑 수를 파이썬 코드로 나타내면 `factorial(2 * num) // (factorial(num) * factorial(num + 1))`이다. 이를 통해 문제를 해결할 수 있다.

 

코드

from math import factorial
from sys import stdin


def catalan(num):
    return factorial(2 * num) // (factorial(num) * factorial(num + 1))


if __name__ == '__main__':
    t = int(stdin.readline())

    for _ in range(t):
        n = int(stdin.readline())

        if n % 2 != 0:
            print(0)
            continue

        print(catalan(n // 2) % 1000000007)