[백준 10422] 괄호 (JAVA)

문제

https://www.acmicpc.net/problem/10422

풀이

DP를 이용해 해결할 수 있습니다.

• 2개일 때
  2.1 : ()

• 4개일 때
  4.1 : (2.1) -> (())
  4.2 : ()2.1 -> ()()

• 6개일 때
  6.1 : ()4.1 -> ()(())
  6.2 : ()4.2 -> ()()()
  6.3 : (4.1) -> ((()))
  6.4 : (4.2) -> (()())
  6.5 : (2.1)2.1 -> (())()

• 8개일 때
  (6.1) (6.2) (6.3) (6.4) (6.5)
  ()6.1 ()6.2 ()6.3 ()6.4 ()6.5
  (2.1)4.1 (2.1)4.2 (4.1)2.1 (4.2)2.1

이런 규칙이 있다는 것을 알 수 있습니다. 괄호를 두고 안에 있을 때 바깥에 있을 때로 구분지어 계산하면 됩니다. 괄호를 이미 하나 사용하기 때문에 8개를 계산하기 위해선 dp[0]dp[6] + ... + d[6]dp[0]을 이용해야 합니다.

코드

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

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        final long MOD = 1000000007;
        int T = Integer.parseInt(br.readLine());

        long[] dp = new long[5001];
        dp[0] = 1;
        dp[2] = 1;

        for (int i = 4; i <= 5000; i+=2) {
            int left = 0, right = i - 2;
            long ans = 0;
            while (left <= right) {
                if (left == right) ans += dp[left] * dp[right];
                else ans += dp[left] * dp[right] * 2;
                ans %= MOD;
                left += 2;
                right -= 2;
            }
            dp[i] = ans;
        }


        for (int t = 1; t <= T; t++) {
            int num = Integer.parseInt(br.readLine());
            sb.append(dp[num]).append('\n');
        }

        System.out.println(sb);
        br.close();
    }
}