220810 - 괄호

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

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

입력

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

출력

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

입출력 예

Input	Output
3 1 4 2	0 1 2

◾ 풀이

1. 해설

동적 프로그래밍 기법을 활용해 각 결과를 저장해 두고 계산 진행.
- 올바른 괄호 문자열을 만드는 방법.
  - 모든 ("올바른 괄호 문자열1")"올바른 괄호 문자열2" 개수의 합.
  - (ex) 길이 4의 올바른 괄호 문자열. : ( )( ), ( ( ) )
    - 길이 0인 올바른 괄호 문자열 : " "
    - 길이 2인 올바른 괄호 문자열 : ( )
    - ( 길이_0 ) 길이_2 : ( " " )( )
    - ( 길이_2 ) 길이_0 : ( ( ) ) " "
    - 총 2개로 올바른 것을 확인

2. 프로그램

dp[] 계산 : 각 인덱스를 길이로 가지는 올바른 문자열의 개수.
- 홀수 길이로는 올바른 괄호 문자열을 만들 수 없음.
- L : 개수를 구하려는 길이
- sum(dp[i] + dp[L-i-2]) (0 <= i <= L-2, i += 2)
- 최종적으로 1000000007로 나눈 나머지 계산
각 테스트 케이스에 대한 L을 입력받아 결과 반환.

# 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;

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

		int T = Integer.parseInt(in.readLine()); // 테스트 케이스

		// 계산 결과를 담을 dp배열.
		// 길이가 0인 경우의 올바른 괄호 개수는 1임을 알 수 있으므로 초기화.
		long[] dp = new long[5001];
		dp[0] = 1;

		// 각 길이로 만들 수 있는 올바른 괄호의 개수 계산.
		for (int i = 2; i <= 5000; i += 2) {
			
            // ( ) 길이 2인 올바른 괄호로 한쪽을 감쌀 것이기 때문에 
            // i-2의 길이로 만들 수 있는 모든 조합 탐색.
			for (int j = i - 2; j >= 0; j -= 2) {
				dp[i] += (dp[j] * dp[i - j - 2]);
				dp[i] %= 1000000007;
			}
		}

		// 각 테스트 케이스에 대해 미리 계산한 dp배열의 결과 반환.
		for (int test_case = 1; test_case <= T; test_case++) {
			int L = Integer.parseInt(in.readLine());
			sb.append(dp[L]).append("\n");
		}

		System.out.println(sb);
	}
}