[DP] 카탈란 수 (백준 10422)

목차

• 1. 서론: 직관의 배신, 괄호의 늪
• 2. 시행착오 1: 단순히 2배로 늘어나지 않는다
• 3. 시행착오 2: 분할의 함정, 중복 카운팅
• 4. 카탈란 수: 조합론의 피보나치
• 5. 해결책: 유일한 기준 ‘(A)B’의 증명
• 6. 구현 디테일
• 7. 최종 코드 및 정석 패턴

1. 서론: 직관의 배신, 괄호의 늪

알고리즘 문제를 풀다 보면 “이건 딱 봐도 규칙이 뻔하네”라고 생각했다가 큰코다치는 경우가 종종 있습니다. 백준 10422번 ‘괄호’ 문제가 바로 그런 문제입니다.

길이가 L인 올바른 괄호 문자열의 개수를 구하는 이 문제는 초반 항 몇 개만 나열해 보면 규칙이 단순해 보입니다. L=2일 때 1개, L=4일 때 2개, L=6일 때 5개… 하지만 L이 커질수록 숫자는 폭발적으로 증가하며, 단순한 등차수열이나 등비수열의 규칙을 따르지 않습니다. 이 문제의 핵심은 단순히 “이전 단계에서 어떻게 커지는가”를 묻는 것이 아니라, “올바른 괄호 문자열의 구조적 정의가 무엇인가”를 묻고 있기 때문입니다. 많은 입문자가 겪는 두 가지 대표적인 시행착오를 통해 그 본질에 접근해 보겠습니다.

2. 시행착오 1: 단순히 2배로 늘어나지 않는다

가장 흔한 첫 번째 접근은 “이전 단계의 문자열에 괄호를 붙이면 되지 않을까?”라는 발상입니다. 길이가 N-2인 문자열들에 ()를 옆에 붙이거나, 전체를 ( )로 감싸는 방식을 떠올립니다.

실패 로직의 예

// [시도 1] 단순 증식 모델
// 논리: dp[i] = dp[i-2] * 2 (옆에 붙이기 + 감싸기?)
if (i % 2 == 0) dp[i] = 2 * dp[i - 2];

기술적 분석

이 접근이 틀린 이유는 구조적 다양성을 과소평가했기 때문입니다. 괄호 문자열은 단순히 선형적으로 증식하지 않습니다. 예를 들어 길이 6을 만들 때, `((()))` (감싸기)와 `()()()` (옆에 붙이기) 외에도, `(())(())` 처럼 균형 잡힌 두 덩어리가 결합하는 형태가 존재합니다. 단순한 2배 연산으로는 이러한 ‘복합 결합’ 형태를 절대 잡아낼 수 없습니다.

3. 시행착오 2: 분할의 함정, 중복 카운팅

단순 증식이 불가능함을 깨달은 개발자는 이제 ‘분할 정복’적 사고를 도입합니다. “길이 `i`를 만들려면, 길이 `j`와 길이 `i-j`를 합치면 되겠네!”라는 생각입니다.

실패 로직의 예

// [시도 2] 단순 분할 모델
// 논리: 임의의 지점 j에서 문자열을 절단하여 결합
for (int j = 2; j < i; j += 2) {
    dp[i] += dp[j] * dp[i - j]; 
}

심층 분석: 중복 카운팅(Overcounting)의 발생 원리

이 로직은 '기준의 부재'로 인해 필연적으로 중복을 발생시킵니다. 구체적인 예시로 길이 6의 ()()()`를 살펴보겠습니다.

• Case A (j=2): 앞쪽 () + 뒤쪽 ()()` → ()()()` 생성
• Case B (j=4): 앞쪽 ()()` + 뒤쪽 () → ()()()` 생성

분명히 같은 문자열임에도 불구하고, 컴퓨터는 이를 '다른 경우'로 인식하여 두 번 카운트합니다. N이 커질수록 괄호 덩어리는 더 잘게 쪼개질 수 있으므로, 중복의 횟수는 기하급수적으로 늘어납니다. 결국 "어디를 자를 것인가?"에 대한 유일하고 절대적인 기준 없이는 DP를 완성할 수 없습니다.

4. 카탈란 수: 조합론의 피보나치

사실 이 문제는 수학적으로 매우 유명한 카탈란 수(Catalan Numbers) 문제입니다. 카탈란 수는 Cn = 1/(n+1) * 2nCn이라는 일반항을 가지며, 다음과 같은 문제들에 공통적으로 등장합니다.

• 올바른 괄호 문자열의 개수: (지금 풀고 있는 문제)
• 이진 트리(Binary Tree)의 개수: 노드가 n개일 때 가능한 트리의 모양
• 볼록 다각형의 삼각형 분할: 대각선을 그어 삼각형으로 나누는 방법의 수

이토록 다양한 분야에 같은 수열이 등장하는 이유는, 이 모든 문제가 "재귀적으로 정의된 구조(Recursive Structure)"를 가지며 "하나의 고정된 기준점(Anchor)"을 통해 문제를 쪼갤 수 있기 때문입니다. 개발자에게 카탈란 수는 '재귀적 분할'의 가장 완벽한 예시입니다.

5. 해결책: 유일한 기준 '(A)B'의 증명

중복을 피하기 위해 우리는 '가장 먼저 닫히는 괄호'라는 개념을 도입해야 합니다. 이것이 바로 (A)B 구조입니다.

S = ( A ) B

모든 올바른 괄호 문자열 S는 다음 세 부분으로 유일하게 분해됩니다.

1. ( ... ) : 맨 처음에 나온 여는 괄호와, 그것과 짝이 되는 닫는 괄호.
2. A : 그 괄호 쌍 안에 갇힌 내부 문자열.
3. B : 그 괄호 쌍이 닫힌 뒤에 남은 외부 문자열.

왜 이 기준은 중복이 없는가? (Uniqueness)

어떤 문자열에서 "첫 번째 여는 괄호의 짝"은 단 하나뿐입니다.
예를 들어 ()()()`에서 첫 번째 (의 짝은 바로 뒤의 )입니다. 4번째나 6번째 )와 짝이 될 수 없습니다.
따라서 S를 (A)B로 쪼개는 방법은 단 한 가지 경우의 수만 존재합니다. 이 '유일성' 덕분에 우리는 마음 놓고 곱셈 법칙을 적용할 수 있습니다.

최종 점화식 도출

전체 길이 i를 만들 때, ( ) 두 글자를 제외한 i-2 길이를 A와 B가 나누어 가집니다.

dp[i] = Sum( dp[A의 길이] * dp[B의 길이] )

(단, A의 길이 + B의 길이 = i - 2)

6. 구현 디테일

논리적 구조를 완성했지만, 마지막 관문이 남아있습니다. 바로 오버플로우(Overflow)입니다. 카탈란 수는 팩토리얼 급으로 증가하기 때문에 i=50만 되어도 long 범위를 초과할 수 있습니다.

연산자 우선순위와 누적의 실수

많은 입문자가 다음과 같이 코드를 작성하여 틀립니다.

// [오류] 덧셈이 계속 누적되어 오버플로우 발생
dp[i] += dp[j] * dp[i-2-j] % MOD;

위 식은 곱셈 결과에만 모듈러 연산을 적용합니다. 하지만 dp[i]에 계속 값을 더하다 보면, dp[i] 자체가 모듈러 값(10억 7)을 초과하게 되고, 결국 나중에는 long 범위조차 뚫고 나가게 됩니다.

정석 구현 패턴

모듈러 연산의 분배 법칙 (A + B) % M = ((A % M) + (B % M)) % M을 기억해야 합니다. 누적되는 합계 전체를 지속적으로 눌러주어야 합니다.

// [정석] 더한 결과 전체에 모듈러 적용
dp[i] = (dp[i] + dp[j] * dp[i-2-j]) % MOD;

7. 최종 코드 및 정석 패턴

집합론적 논리(카탈란 수)와 대수학적 테크닉(모듈러 연산)을 결합한 최종 솔루션입니다.

[카탈란 DP 작성 공식]

1. 기저 사례 설정: dp[0] = 1 (빈 문자열도 1가지 경우로 취급해야 곱셈 성립)
2. 2중 루프 구성: 전체 길이 i(2부터 5000)와 내부 길이 j(0부터 i-2)
3. 점화식 적용: (A)B 구조에 따라 dp[j] * dp[i-2-j] 수행
4. 안전한 연산: 매 덧셈마다 % MOD 수행, 곱셈 시 long 형변환 고려

import java.util.*;

public class Main {
    // 10억 7 (소수)
    static final long MOD = 1_000_000_007L;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 테스트 케이스 개수 T 입력
        int T = sc.nextInt();
        
        // 1. DP 테이블 전처리 (Pre-computation)
        // 매 테스트 케이스마다 새로 계산하면 비효율적이므로 최대치까지 미리 계산
        long[] dp = new long[5001];
        
        // 기저 사례: 길이가 0인 경우 (A가 비었거나 B가 빈 경우)
        dp[0] = 1; 

        // i: 전체 길이 (홀수는 불가능하므로 2부터 짝수만 증가)
        for (int i = 2; i <= 5000; i += 2) {
            // j: (A) 부분인 괄호 '안'의 길이 (0부터 i-2까지 짝수만)
            for (int j = 0; j <= i - 2; j += 2) {
                // 점화식: dp[i] = Sum(dp[A] * dp[B])
                // A의 길이 = j
                // B의 길이 = i - 2(괄호두개) - j
                
                // [중요] 곱셈 결과가 long 범위를 넘지 않더라도,
                // 누적합 과정에서 오버플로우를 막기 위해 매번 MOD 연산 수행
                dp[i] = (dp[i] + dp[j] * dp[i - 2 - j]) % MOD;
            }
        }

        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int L = sc.nextInt();
            // 2. 쿼리 처리
            // 홀수 길이는 올바른 괄호를 만들 수 없음 -> 0 출력
            if (L % 2 != 0) {
                sb.append(0).append("\n");
            } else {
                sb.append(dp[L]).append("\n");
            }
        }
        System.out.println(sb);
    }
}

백준 10422번은 단순한 DP 문제를 넘어, '문제를 쪼개는 기준을 어떻게 잡을 것인가'에 대한 깊은 통찰을 요구합니다. 시행착오를 통해 배운 (A)B 구조는 앞으로 여러분이 마주할 수많은 '트리 구조'나 '분할 문제'에서 강력한 무기가 되어줄 것입니다.