[BOJ] 백준 10422 : 괄호 (java)

🧪 10422 괄호

---

난이도 : 🌟 골드 4
유형 : 동적 프로그래밍 (DP)

10422번: 괄호

 

📝 문제

---

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

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

 

 

입력

 

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

 

출력

 

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

 

🧐 핵심 로직

---

• 카탈란 수를 활용하여 dp를 구성 해야한다. 카탈란 수에 따르면 n 쌍의 괄호가 잘 짜인 방법의 수를 Cn 이라고 한다. 완전한 괄호를 구하는 방법은 아래와 같이 나타낼 수 있고, 이를 dp로 나타내면 된다.

카탈란 수에서 위와같은 점화식이 나오는 이유는 이미 한쌍의 괄호가 있다고 가정하고, 괄호안에 넣을 수 있는 경우 * 괄호 밖에 두는 경우로 점화식을 세웠다. 위의 방법에 따라 dp로 나타냈다.

 

dp[4] = 2 ☛  ("")(), (())""  ☛  (dp[0])dp[2] +(dp[2])dp[0]

dp[6] = 5 ☛  ("")()(), ("")(()), (())(), (()())"", ((()))"" ☛ (dp[0])dp[4] + (dp[2])dp[2] + (dp[4])dp[4]

dp[8] = 14 ☛ dp[0]*dp[6] + dp[2]*dp[4] + dp[4]*dp[2] + dp[6]dp[0]

 

💻 최종 코드 (156 ms)

---

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

public class Main {

    static int l;
    static long[] dp;
    public static void main(String[] args) throws Exception {

//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));

        int t = Integer.parseInt(br.readLine());
        int num = 1;

        dp = new long[5001];
        dp[0] = 1;
        dp[2] = 1;

        for (int i = 2; i < 2501; i++) {
            for (int j = 0; j < i; j++) {
                dp[i * 2] += (dp[j * 2] * dp[(i - 1 - j) * 2]);
                dp[i * 2] %= 1000000007L;
            }
        }

        for (int i = 1; i <= t; i++) {
            l = Integer.parseInt(br.readLine());

            if (l % 2 == 1) {
                System.out.println(0);
                continue;
            }

            System.out.println(dp[l]);
        }

        br.close();
    }
}