BOJ 10422 괄호 (Java)

문제 탐색하기

• (, ) 문자로만 이루어진 문자열을 괄호 문자열이라 한다.
• ()는 올바른 괄호 문자열이다.
• S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다.
• S와 T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 ST도 올바른 괄호 문자열이다.
• (()())()은 올바른 괄호 문자열이지만 (()은 올바른 괄호 문자열이 아니다.

코드 설계하기

어떠한 규칙에 의해 이후의 값이 정해지므로, 점화식으로 값을 도출할 수 있다. -> DP

구현 방법

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

점화식

• dp[4] = dp[2] * dp[0] + dp[0] * dp[2]
• dp[6] = dp[4] * dp[0] + dp[2] * dp[2] + dp[0] * dp[4]
• 점화식
  • dp[2n] = ∑ (dp[2i] * dp[2(n - 1 - i)]) for i = 0 to n - 1

시간 복잡도

O(n) => 약 5000회

정답 코드 (Java)

import java.io.*;  
  
public class Main {  
    public static void main(String[] args) throws IOException{  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));  
  
        int t = Integer.parseInt(br.readLine());  
        long[] dp = new long[5001];  
        dp[0] = 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] %= 1_000_000_007L;  
            }  
        }  
  
        for(int i=0; i < t; i++) {  
            int a = Integer.parseInt(br.readLine());  
            if (a % 2 != 0) { // 홀수인 경우
                bw.write("0\n");
            } else {
                bw.write(dp[a] + "\n");
            }
        }  
  
        bw.flush();  
        bw.close();  
        br.close();  
    }  
}