10422번- 괄호(dp, 카탈랑 수)

문제:

'(' , ')'문자로만 이뤄진 문자열이 있다.
길이가 L인 올바른 괄호 문자열을 구하여라.

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

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

 

풀이:

카탈란 수라는 개념을 코드로 작성하는 문제이다. 아래 블로그에 잘 설명이 되어있다.

[알고리즘] 카탈란 수(Catalan number) (tistory.com)

괄호를 직접 그리며 설명을 해보겠다.

괄호의 수	가능한 괄호 문자열
0
2	( )
4	( ) ( ) (())
6	( ) ( ) ( ) (()) ( ) ( ) (()) (( )( )) ((()))
8	( ) ( ) ( ) ( ) (()) ( ) ( ) ( ) (()) ( ) ( ) ( ) (()) (()) (()) ( ) ((())) ((())) ( ) ( ) (( )( )) (( )( )) ( ) (( ) ( ) ( )) ((()) ( )) (( ) (())) ((( )( ))) (((())))

위 표를 보면 일정한 규칙성이 보일 것이다.

문제의 핵심은 규칙성을 엉뚱하게 찾지 않고, 카탈란 수라는 것을 알아채는 것에 있다.

괄호의 수가 2개와 4개는 너무 간단하니, 6개일 때를 자세하게 살펴보자.

 

괄호의 수가 하나 늘어난다면, 이전 경우보다 그 괄호 안에 넣는 경우의 수가 늘어나는 것이다.

무슨말인지 어렵다면 아래 설명을 보자.

괄호의 수가 6개일때, 아래와 같은 괄호 문자열을 만들 수 있을 것이다.

1. 새로운 괄호 안에 2쌍의 괄호, 밖에 0쌍의 괄호

(( ) ( ))

((()))

2. 새로운 괄호 안에 1쌍의 괄호, 밖에 1쌍의 괄호

( ( ) ) ( )

3. 새로운 괄호 안에 0쌍의 괄호, 밖에 2쌍의 괄호

( ) ( )

( ) ( ( ) )

문제를 위와 같이 접근했다면, 이미 코드를 작성할 수 있을 것이다.

예제를 하나더 살펴보자.

 

괄호의 수가 8개일때, 아래와 같은 괄호 문자열을 만들 수 있을 것이다.

1. 안에 3쌍, 밖에 0쌍

( ( ) ( ) ( ) )
( (()) ( ) )
( ( ) (()) )
( (( )( )) )
( ((())) )

2. 안에 2쌍, 밖에 1쌍

( ( ) ( ) ) ( )
( (()) ) ( )

3. 안에 1쌍, 밖에 2쌍

( () ) ( ) ( )
( () ) (())

4. 안에 0쌍, 밖에 3쌍

( ) ( ) ( ) ( )
( ) (()) ( )
( ) ( ) (())
( ) (( )( ))
( ) ((()))

 

6가지일 때와 8가지일때 경우를 놓고 보면 일정한 규칙이 보인다.

6가지 일때는 ( C2 * C0 ) + ( C1 * C1 ) + ( C0 * C2 ) = 5

8가지 일때는 ( C3 * C0 ) + ( C2 * C1 ) + ( C1 * C2 ) + ( C0 * C3 ) = 14

C는 카탈랑 수를 나타내는 기호이다.

 

또한 각 카탈랑 수를 나타내는 값은 표에 저장되어 있다.

괄호의 수	가능한 괄호 문자열
0
2	( )
4	( ) ( ) (())
6	( ) ( ) ( ) (()) ( ) ( ) (()) (( )( )) ((()))
8	( ) ( ) ( ) ( ) (()) ( ) ( ) ( ) (()) ( ) ( ) ( ) (()) (()) (()) ( ) ((())) ((())) ( ) ( ) (( )( )) (( )( )) ( ) (( ) ( ) ( )) ((()) ( )) (( ) (())) ((( )( ))) (((())))

 

이제 문제를 풀기 위한 과정은 모두 마쳤으니, 위의 풀이를 활용해 메서드를 작성해보겠다.

static long[] dp;

static void parentheses() {
    dp[0] = 1;
    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-j-1)*2];
            dp[i*2] %= 1000000007;
        }
    }
}

dp는 5001 크기의 배열로 초기화 해줬다.

dp[0] = 1이며, 문자열의 길이가 0일때는 그냥 그대로 두면, 올바른 문자열이기 때문이다.

위에서 소개한 표를 보면, dp[0] = 1, dp[2] = 1, dp[4] = 2이다.

 

dp[6]를 위의 메서드에 따라 계산하자면,

( dp[0] * dp[4] ) + ( dp[2] * dp[2] ) + ( dp[4] * dp[0] ) = 2 + 1 + 2 = 5 이다.

실제로 우리가 이전 풀이에서 작성한 식인 ( C2 * C0 ) + ( C1 * C1 ) + ( C0 * C2 ) = 5 과 동일하다.

 

dp[8]도 위의 코드에 따라 계산하자면,

( dp[0] * dp[6] ) + ( dp[2] * dp[4] ) + ( dp[4] * dp[2] ) + ( dp[6] * dp[0] ) = 5 + 2 + 2 + 5 = 14 이다.

이 또한  ( C3 * C0 ) + ( C2 * C1 ) + ( C1 * C2 ) + ( C0 * C3 ) = 14  과 동일하다.

 

전체코드:

import java.util.Scanner;

public class 괄호_10422 {
    static int T;
    static int[] L;
    static long[] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        L = new int[T];

        for (int i = 0; i < T; i++) {
            L[i] = sc.nextInt();
        }

        dp = new long[5001];

        parentheses();

        for (int i = 0; i < T; i++) {
            System.out.println(dp[L[i]]);
        }
    }

    static void parentheses() {
        dp[0] = 1;
        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-j-1)*2];
                dp[i*2] %= 1000000007;
            }
        }
    }
}

 

시행착오:

아.. 규칙을 잘못 찾았었다.

어느 정도 비슷한 규칙이었지만, 밖에 있는 괄호를 재배치하지 않았다.

밖에 두개의 괄호가 있다면, ( ) ( ), ( () ) 이렇게 배치 될 수 있는데,

나는 ( ) ( ) 배치 했었다.

그 결과 아래처럼 잘못된 규칙을 찾게 되었다.

0
1

2
num = 0
0 + 1 = 1
( )

4
num = 1
1 + 1 = 2
( ) ( )
(()) -- 2

6
num = 2
1 + 2 + 2 = 5
( ) ( ) ( )
(()) ( ) -- 2
( ) (()) -- 2
(( )( )) -- 4
((())) -- 4

8
num = 5
1 + 3 + 4 + 5 = 13
( ) ( ) ( ) ( )
(()) ( ) ( ) -- 2
( ) (()) ( ) -- 2
( ) ( ) (()) -- 2
( ) ((())) -- 4
((())) ( ) -- 4
( ) (( )( )) -- 4
(( )( )) ( ) -- 4
(( ) ( ) ( )) -- 6
((()) ( )) -- 6
(( ) (())) -- 6
((( )( ))) -- 6
(((()))) -- 6

10
1+ 4 + 6 + 10 + 13 = 34
( ) ( ) ( ) ( ) ( )
(()) ( ) ( ) ( ) -- 2
( ) (()) ( ) ( ) -- 2
( ) ( ) (()) ( ) -- 2
( ) ( ) ( ) (()) -- 2
( ) ( ) ((())) -- 4
( ) ((())) ( ) -- 4
((())) ( ) ( ) -- 4
( ) ( ) (( )( )) -- 4
( ) (( )( )) ( ) -- 4
(( )( )) ( ) ( ) -- 4
( ) (( ) ( ) ( )) -- 6
(( ) ( ) ( )) ( ) -- 6
( ) ((()) ( )) -- 6
((()) ( )) ( ) -- 6
( ) (( ) (())) -- 6
(( ) (())) ( ) -- 6
( ) ((( )( ))) -- 6
((( )( ))) ( ) -- 6
( ) (((()))) -- 6
(((()))) ( ) -- 6
( ( ) ( ) ( ) ( ) ) -- 8
( (()) ( ) ( ) ) -- 8
( ( ) (()) ( ) ) -- 8
( ( ) ( ) (()) ) -- 8
( ( ) ((())) ) -- 8
( ((())) ( ) ) -- 8
( ( ) (( )( )) ) -- 8
( (( )( )) ( ) ) -- 8
( (( ) ( ) ( )) ) -- 8
( ((()) ( )) ) -- 8
( (( ) (())) ) -- 8
( ((( )( ))) ) -- 8
( (((()))) )  -- 8

12 - 1 + 5 + 8 + 15 + 26 + 34 = 89

그렇게 나온 잘못된 코드는 아래와 같다.

import java.util.Scanner;

public class 괄호_10422_틀림 {
    static int T;
    static int[] L;
    static long[] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        L = new int[T];

        for (int i = 0; i < T; i++) {
            L[i] = sc.nextInt();
        }

        dp = new long[5001];

        parentheses();

        for (int i = 0; i < T; i++) {
            System.out.println(dp[L[i]]);
        }
    }

    static void parentheses() {
        dp[2] = 1;
        long sum = 1;
        for (int i = 4; i <= 5000; i+=2) {
            dp[i] = dp[i-2] + sum; // 2 5 13 34
            sum += dp[i]; // 3 8 21 55
        }
    }
}

 

규칙을 좀 더 집중해서 찾으면, 실수를 줄일 수 있을 것 같다.

그래도 카탈랑 수라는 개념을 알게 되었다. 비슷한 문제를 풀게된다면 맞출 수 있을 것 같다.