[백준] 10422 괄호 - 파이썬

문제

https://www.acmicpc.net/problem/10422

10422번: 괄호

‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 ST도 올바른 괄호 문자열이다. (()())()은 올바른 괄호 문자열이지만 (()은 올바른 괄호 문자열이 아니다. 괄호 문자열이 주어졌을 때 올바른 괄호 문자열인지 확인하는 방법은 여러 가지가 있다.

하지만 우리가 궁금한 것은 길이가 L인 올바른 괄호 문자열의 개수이다. 길이 L이 주어졌을 때 길이가 L인 서로 다른 올바른 괄호 문자열의 개수를 출력하는 프로그램을 만들어 보자.

입력

첫 번째 줄에 테스트케이스의 개수를 나타내는 T (1 ≤ T ≤ 100)가 주어진다. 두 번째 줄부터 각 테스트케이스마다 괄호 문자열의 길이를 나타내는 L이 주어진다. (1 ≤ L ≤ 5000) 

출력

각 테스트 케이스에 대해 길이가 L인 올바른 괄호 문자열의 개수를 1,000,000,007로 나눈 나머지를 출력하시오.

 

 

---

풀이

 

dp 짱어렵다,,.,.

1, 2, 3 더하기 4 문제처럼 앞에 괄호 한 쌍을 추가하는 경우, 뒤에 괄호 한 쌍을 추가하는 경우

괄호 사이에 기존 문자열을 넣는 경우 이런식으로 풀어보려했는데

 

겹치는 경우의 수도 많고 예외가 많아 그렇게 푸는 것이 아닌 듯 했다.

다른 생각은 나지 않아 다른 분의 풀이를 봤다.

 

https://ghqls0210.tistory.com/122

문제에서 올바른 문자열 S와 T를 합친 ST도 올바른 문자열이라 언급한 것이 중요한 포인트였다.

 

만약 100자의 문자열을 검사한다고 가정하면 100자를 S와 T로 나누는 것이다.

첫 괄호의 시작점은 맨 처음자로 정해져있고, 닫히는 괄호의 위치를 i라고 한다면

괄호 사이에 포함되는 문자열의 길이는 i-2이다. 이 문자열이 괄호를 씌운 S가 된다.

그리고 뒤에 남은 문자열의 길이는 L-i가 된다. 이 문자열이 T에 해당한다.

 

(S)에 해당하는 경우의 수 dp[i-2]와 T에 해당하는 경우의 수 dp[L-i]를 곱하면 전체 경우의 수가 나온다.

오버플로가 나지 않게 하기 위해 매번 10000007로 나눠준다.

 

import sys
input = sys.stdin.readline

n = int(input())
case = [int(input()) for _ in range(n)]

dp = [0]*5001
dp[0] = 1
dp[2] = 1

for c in range(4, max(case)+1):
    if c % 2 != 0: #홀수라 계산 안해줘도 됨
        continue
    for i in range(2, c+1):
        dp[c] += dp[i-2]*dp[c-i]
    dp[c] %= 1000000007

for c in case:
    print(dp[c])

 

보고 나니 알겠는데.. 너무 어렵다