테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 괄호 ======

===== 풀이 =====
  * 올바른 괄호의 갯수는 [[ps:카탈랑 수]]로 표현되는 대표적인 예제이다.
    * 왜 이게 카탈랑 수가 되는지는, [[:ps:problems:programmers:12929|올바른 괄호의 갯수]]에 간략히 설명했다
  * L이 홀수이면, 올바른 괄호가 만들어질 수 없으니 0을 출력하고 L이 짝수이면, L/2번째 카탈랑 수를 출력하면 된다
  * 테스트 케이스가 여러개이므로, 매번 L/2번째 카탈랑 수를 계산하는 것보다, 전처리 단계에서 범위 내의 카탈랑수를 미리 모두 계산해 놓고 (O(n)에 가능하다), 테스트 케이스를 입력받으면서 계산해 놓은 카탈랑 수를 출력해야 효율적이다. 이렇게 하면, O(L+T)에 해결 가능하다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 10422. 괄호".

- Problem link: https://www.acmicpc.net/problem/10422
- Solution link: http://www.teferi.net/ps/problems/boj/10422
"""

MOD = 1_000_000_007
MAX_SIZE = 25000


def main():
    inv = [0, 1]
    for i in range(2, MAX_SIZE + 3):
        inv.append(-(MOD // i) * inv[MOD % i])
    catalan_nums = [1]
    for i in range(MAX_SIZE):
        catalan_nums.append(2 * (2 * i + 1) * inv[i + 2] * catalan_nums[i] %
                            MOD)

    T = int(input())
    for _ in range(T):
        L = int(input())
        print(0 if L % 2 else catalan_nums[L // 2])


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_4}}