BOJ(괄호) 10422

작성일 | In

  • 길이 L이 주어졌을 때, 길이가 L인 올바른 괄호 문자열의 개수를 구하는 문제

  • 첫 번째 글자와 대응하는 ‘)’는 어디에 있을까? -> 알 수 없다
  • 모르는 경우에는 변수를 써야 한다.
  • 따라서 그 글자를 i번째 글자라고 한다.
  • 그 사이에도 올바른 괄호 문자열이 나와야 한다
  • 왼쪽은 i-2, 오른쪽은 L-i
  • 이 경우, 각각의 올바른 괄호 문자열 당,경우의 수는 이 두 개를 곱한 것을 누적해주면 된다.

2번째 방법

  • D[N][o] : 길이가 N인 괄호 문자열, (올바른이 빠짐), 짝이 맞지 않는 여는 괄호의 개수 : O개
  • 올바른 괄호 문자열은 짝이 맞지 않는 여는 괄호가 있으면 안된다.

  • 길이가 L인 올바른 괄호 문자열은 D[L][0]

  • 괄호 문자열이라면 제일 마지막에 올 수 있는게 여는 괄호, 또는 닫는 괄호

  • 여는 괄호 였으면, 길이가 N인데, 길이는 N-1이 되겠고, 전체가 짝이 맞지 않는 여는 괄호가 O개 였는데, 닫는 괄호 때문에, 짝을 맞춰 버렸다.

top down

mod = 1000000007
d = [-1] * 5001
def go(n):
    if n == 0:
        return 1
    if d[n] >= 0:
        return d[n]
    d[n] = 0
    for i in range(2, n+1, 2):
        d[n] += go(i-2) * go(n-i)
        d[n] %= mod
    return d[n]

t = int(input())
for _ in range(t):
    n = int(input())
    if n%2 == 0:
        print(go(n))
    else:
        print(0)

bottom up

mod = 1000000007
d = [[0] * 5001 for _ in range(5001)]
d[0][0] = 1
for i in range(1, 5001):
    for j in range(i+1):
        if j+1 <= i:
            d[i][j] += d[i-1][j+1]
        if j-1 >= 0:
            d[i][j] += d[i-1][j-1]
        d[i][j] %= mod
t = int(input())
for _ in range(t):
    n = int(input())
    print(d[n][0])

참고자료 codeplus

0%