Problem Solving/Baekjoon

[백준] 10422 괄호 - Dynamic Programming / Java

graycode 2022. 10. 21. 14:30

• 문제 링크

 

10422번: 괄호

‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호

www.acmicpc.net

 

• 풀이 과정

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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));

        long[] dp = new long[2501];
        dp[0] = dp[1] = 1;

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

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

        while (t-- > 0) {
            int l = Integer.parseInt(br.readLine());
            bw.write((l % 2 == 0 ? dp[l / 2] : 0) + "\n");
        }

        bw.flush();
    }

}