[백준 10422] 괄호 (JAVA)

10138 단어 algorithmbojalgorithm

문제


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

좋은 웹페이지 즐겨찾기