백준 BOJ 13174 괄호 풀이 (카탈란 삼각형, Diamond IV)

백준 BOJ의 13714번 문제인 '괄호'의 풀이를 해보겠습니다.

 

Solved.ac 기준 Diamond IV의 난이도에 해당하는 문제이고, 문제 분류는 '조합론'으로 되어있습니다.

 

 

BOJ 13174 : 괄호

올바른 괄호 문자열을 ( ) ( ( ) ( ) )과 같이, 괄호가 문법에 어긋나지 않게 열고 닫힌 문자열이라고 정의합니다.

이러한 괄호 문자열 중에서 길이 2N인 "대칭" 괄호 문자열에 대해서 생각해봅시다.

열고 닫는 괄호의 쌍에 맞게 K가지 색을 이용하여 괄호의 색을 칠한다고 할 때, 존재하는 괄호 문자열의 수는 몇 가지가 있는지 구하여 그 값의 mod 1,000,000,007을 구하는 문제입니다.

 

문제에 대한 더 자세한 설명과 조건은 BOJ의 13174번 문제를 직접 참고하시면 좋을 것입니다.

여기서는 풀이에 중점을 두고 해설을 다루어보도록 하겠습니다.

 

 

 

주어진 조건에 해당하는 문자열은 대칭 문자열이므로, 반으로 나눠서 왼쪽만 생각해봅시다.

그러면 이 문자열은 모든 접두사, 즉 왼쪽에서부터 읽다가 어느 지점까지 읽어도 )가 (보다 많이 나오지 않는 문자열이라는 것을 알 수 있습니다.

 

이러한 경우의 수에 대응되는 수열이 존재하는데, 이를 '카탈란 수'라고 부릅니다.

정확히는 '카탈란 삼각형(Catalan's Triangle)'의 일부 항에 해당하는 수들입니다.

 

 

 

카탈란 삼각형에서의 C(n, k)는 '어떤 접두사도 Y과 X보다 많지 않은, n개의 X와 k개의 Y로 이루어진 문자열의 수'로 정의됩니다.

이를 수식으로 표현하면 C(n, k) = (n-k+1)/(n+1) * n+k C k가 됩니다.

 

이에 대한 증명은 (0, 0)에서 (n, k)로 격자점 이동을 하는 경우의 수 중 특정 경계선을 넘지 않는 조건을 추가하여 일대일 대응되는 수를 조합으로 구함으로써 가능합니다.

해당 설명은 위키피디아의 'Catalan's Triangle' 문서에서 확인할 수 있으며 여기에서는 풀이만 하도록 하겠습니다.

 

 

 

문제 입력에서의 N, K와 위의 C(n, k)에서의 n과 k는 다른 n과 k이므로 문제의 기호들을 기준으로 설명하겠습니다.

 

정리해보면 위와 같은 수식으로 답을 얻어낼 수 있습니다.

먼저 첫 번째 항은 N개의 문자 모두 '('로 이루어진 경우이며 각각을 K가지 색으로 칠할 수 있으므로 위와 같이 얻어집니다.

두 번째 항은 N-1개의 '('와 1개의 ')'로 이루어진 항이므로, C(N-1, K)에 해당하며 여기에서 한 개의 ( ) 쌍은 같은 색으로 칠해주어야 하기 때문에 지수가 1 감소한 K^(N-1)가지 방법으로 색을 칠할 수 있습니다.

 

이러한 방식으로 계산해나가다가, n이 int((N+1)/2)까지 감소할 때까지 이를 반복해서 더해주면 됩니다.

이는 ' ) '의 수는 ' ( '보다 많이 나올 수 없기 때문에 N이 짝수인 경우는 N/2개만 나올 수 있고, N이 홀수인 경우는 ' ( '보다 한 개 적게 나올 수 있기 때문입니다.

 

따라서 위와 같은 수식대로 값을 계산해주면 됩니다.

이 때 주의할 점은 오버플로우를 방지하기 위해 매 연산마다 % mod를 해주는 것이고, 또한 분모는 모듈로 역원인 a^(mod - 2)를 곱해서 해결해주면 됩니다.

 

이제 위의 설명을 코드로 구현해보도록 하겠습니다.

 

 

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

long long fac[2000001];
long long kPow[1000001];

long long fastPow(long long ret, int exp) {
    if(exp == 0) return 1;
    else if(exp == 1) return ret;

    if(exp % 2 == 0) {
        long long temp = fastPow(ret, exp/2);
        return (temp * temp) % MOD;
    }
    else {
        long long temp = fastPow(ret, exp - 1);
        return (temp * ret) % MOD;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, K; cin >> N >> K;

    fac[0] = fac[1] = 1;
    for(int i=2; i<=N+K; i++)
        fac[i] = (fac[i-1] * i) % MOD;

    kPow[0] = 1, kPow[1] = K;
    for(int i=2; i<=N; i++)
        kPow[i] = (kPow[i-1] * K) % MOD;

    long long ans = 0;
    for(long long i=N; i>=(N+1)/2; i--) {
        long long j = N - i;

        long long temp = (i-j+1) * fac[i+j] % MOD;
        temp = temp * fastPow((fac[i+1] * fac[j]) % MOD, MOD-2) % MOD;
        temp = temp * kPow[i] % MOD;

        ans = (ans + temp) % MOD;
    }

    cout << ans;
}

 

fastPow 함수는 거듭제곱을 빠르게 수행하기 위해 만들어진 함수입니다.

분모를 곱할 때 모듈로 역원으로 빼서 곱하기 때문에 MOD-2 = 1,000,000,005 제곱을 로그 시간에 수행하기 위해서입니다.

나머지는 위에서 정리한 수식과 경계에 따라서 계산해주기만 하면 쉽게 답을 얻을 수 있습니다.

 

 

 

제출해보면 위와 같이 144ms 정도에 모든 테스트케이스를 통과할 수 있습니다.