[JAVA][BOJ][G4] 10422. 괄호

10422번: 괄호

문제

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

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

입력

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

출력

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

풀이

/*
 * 입력
 * 1. 테스트 케이스 T
 * 2. 괄호 문자열의 길이를 나타내는 L
 * 출력
 * 1. 길이가 L인 올바른 괄호 문자열의 개수를 1,000,000,007로 나눈 나머지
 * 
 * >> 첫번째 (와 i번째 ) 사이에 dp[i-2]개의 경우의 수 생김
 * i 이후의 문자열에는 dp[L-i]개의 경우의 수 생김
 * 
 * dp[i*2] += dp[j*2]*dp[(i-1-j)*2];
 */

코드

package 카탈란수;

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

public class G4_10422_괄호 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

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

		long[] dp = new long[5001];
		
		dp[0] = 1;
		dp[2] = 1;
		
		for(int i = 2; i <= 2500; 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 = 0; i < T; i++) {
			int L = Integer.parseInt(br.readLine());
			sb.append(dp[L]).append("\n");
		}
		
		System.out.println(sb);

	}

}

결과

 

#자바 #java #boj #백준 #알고리즘