[BOJ/백준] 10422 - 괄호

10422번: 괄호

---

2차원 DP

 

독립괄호 : 좌우로 분리 가능

비독립괄호 : 좌우리 분리 불가능

---

---

• 제목

괄호

---

• 조건

시간 제한 : 2 초

메모리 제한 : 256 MB 

---

• 문제

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

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

---

• 입력

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

---

• 출력

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

---

예제 입력1	예제 출력1
3 1 2 4	0 1 2

---

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int size = 5000;
        long mod = 1_000_000_007;
        long[][] dp = new long[size + 1][2];
        dp[2][0] = dp[4][0] = dp[4][1] = 1;
        for(int i = 6; i <= size; i += 2){
            dp[i][0] = dp[i - 2][0] + dp[i - 2][1];
            dp[i][0] %= mod;
            for(int j = 2; j < i; j += 2){
                dp[i][1] += ((dp[i - j][0] + dp[i - j][1]) % mod) * dp[j][0];
                dp[i][1] %= mod;
            }
        }
        for(int i = 0; i < N; i++){
            int L = Integer.parseInt(br.readLine());
            System.out.println((dp[L][0] + dp[L][1]) % mod);
        }
    }
}