사용자 도구

사이트 도구


ps:problems:boj:10422

괄호

ps
링크acmicpc.net/…
출처BOJ
문제 번호10422
문제명괄호
레벨골드 4
분류

수학, 카탈랑 수

시간복잡도O(n+T)
인풋사이즈n<=5000, T<=100
사용한 언어Python
제출기록31508KB / 100ms
최고기록60ms
해결날짜2020/11/16

풀이

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

코드

"""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()

토론

댓글을 입력하세요:
G P C K R
 
ps/problems/boj/10422.txt · 마지막으로 수정됨: 2021/01/21 15:36 저자 teferi