[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[0]  = 1  ☛  "" 빈공간

dp[2] = 1   ☛  () 

 

시뮬레이션

홀수로는 올바른 괄호를 생성할 수 없다. 2의 배수 단위로 시뮬레이션을 돌려보자.

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]

 

이런식으로 i개일 때, 새로 생성되는 괄호 ()를 제외하고 총 i-2의 괄호 경우를 고려해서 설계해주면 된다.

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

 

풀이 코드 

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int t = Integer.parseInt(br.readLine());
		long[] 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=0; i<t; i++) {
			int a = Integer.parseInt(br.readLine());
			System.out.println(dp[a]);
		}
	}
}