[BOJ G4][#DP]10422번 괄호

괄호 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

10174

3111

2301

30.157%

문제

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

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

입력

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

출력

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

예제 입력 1 복사

3
1
2
4

예제 출력 1 복사

0
1
2

 

 

📝 풀이

문제를 보고 생각한 것은 Bottom-Up 방식으로 진행하는 것이였다.

 

일단 괄호의 기본 제안부터 생각하자

1. 홀수 수는 무조건 성립을 안한다. (괄호는 2개의 한쌍이므로 1개가 남으면 무조건 성립이 안하기 때문)
2. 첫번째에 오는 것은 무조건 "(" 여야 한다.(이것도 괄호의 특징)

Bottom-UP 방식으로 처음이 (이면 그 다음은 (, )가 올 수 있다. 그 다음도 똑같이 진행한다.
여기서 알아야 할 점은 "(" 와 ")"은 각각 1과 -1로 치환하면 쉽게 계산할 수 있다. 
그래서 경우의 수를 구하려면 마지막 0이 나오는 것을 찾으면 된다.

import java.io.*;

public class Main {
    static final int MOD = 1_000_000_007;
    static long[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        int[] queries = new int[T];
        int maxL = 0;
        for (int i = 0; i < T; i++) {
            queries[i] = Integer.parseInt(br.readLine());
            if (queries[i] > maxL) maxL = queries[i];
        }

        dp = new long[maxL + 1][maxL + 1];

        dp[0][0] = 1;

        for (int i = 0; i < maxL; i++) {
            for (int j = 0; j <= i; j++) {
                if (dp[i][j] > 0) {
                    if (j + 1 <= maxL) {
                        dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % MOD;
                    }
                    if (j > 0) {
                        dp[i + 1][j - 1] = (dp[i + 1][j - 1] + dp[i][j]) % MOD;
                    }
                }
            }
        }

 
        for (int query : queries) {
            if (query % 2 != 0) {
                System.out.println(0);
            } else {
                System.out.println(dp[query][0]);
            }
        }
    }
}

 

 

그러나 이 방법에도 단점이 존재한다. 메모리가 어마무시하게 늘어난다 ㅋㅋㅋ

📝 카탈리 수

 카탈리 수는 수학에서 중요한 조합적 문제를 해결하는 데 사용하는 수열이다.

import java.io.*;

public class Main {
    static final int MOD = 1_000_000_007;
    static long[] catalan;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        // Find maximum L
        int maxL = 0;
        int[] queries = new int[T];
        for (int i = 0; i < T; i++) {
            queries[i] = Integer.parseInt(br.readLine());
            if (queries[i] > maxL) {
                maxL = queries[i];
            }
        }

        // If maxL is odd, we can return 0 for those cases
        if (maxL % 2 != 0) {
            for (int i = 0; i < T; i++) {
                System.out.println(0);
            }
            return;
        }

        // Compute Catalan numbers up to maxL/2
        int maxN = maxL / 2;
        catalan = new long[maxN + 1];
        catalan[0] = 1;

        for (int i = 1; i <= maxN; i++) {
            catalan[i] = catalan[i - 1] * (2 * (2 * i - 1)) % MOD;
            catalan[i] = catalan[i] * modInverse(i + 1, MOD) % MOD;
        }

        // Output results for each query
        for (int query : queries) {
            if (query % 2 != 0) {
                System.out.println(0);
            } else {
                System.out.println(catalan[query / 2]);
            }
        }
    }

    // Function to compute modular inverse using Fermat's little theorem
    static long modInverse(long a, long m) {
        return power(a, m - 2, m);
    }

    // Function to compute (x^y) % p using modular exponentiation
    static long power(long x, long y, long p) {
        long res = 1;
        x = x % p;
        while (y > 0) {
            if ((y & 1) == 1) res = (res * x) % p;
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }
}

훨씬 좋아졌다..... 나중에 포스팅해보도록 할 것