/ BOJ

BOJ_10422_괄호_JAVA

문제 : 괄호

링크 : BOJ_10422_괄호x

접근 방식

이 문제의 정답의 수열은 카탈란 수를 따라가지만, 괄호의 규칙 중에 괄호가 완결이 난 상태에서만 결정이 나기 때문에 문자열의 길이가 1일 경우에는 정답이 0이 된다. 이 경우만 주의한 채로 N번째 카탈란 수를 구하면 쉽게 풀 수 있는 문제이다.

소스 코드

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

public class BOJ_10422_괄호 {

	static final int MOD = 1000000007;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

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

		long[] dp = new long[5001];

		dp[0] = 1;
		dp[1] = 0;
		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] = dp[i*2] % MOD;
			}
		}

		for (int tc = 0; tc < T; tc++) {

			int N = Integer.parseInt(in.readLine());

			System.out.println(dp[N]);

		}
	}
}

이 문제의 카테고리가 카탈란 수로 되어있었기 때문에 쉽게 풀 수 있었던 것 같다. 모르는 상태에서 풀려면 많은 시간 해메고 있었을 것이다.