BOJ 24231 해석

https://www.acmicpc.net/problem/24231

24231번: 해석

컨디션 난조로 3주만에 처음으로 문제를 풀어봤다.

 

어떠한 암호 문자열이 주어졌을 때, 이 암호 문자열을 분해하는 방법은 아래의 두 가지 방법이 있다

• AB - A와 B모두 올바른 암호 문자열. 대응 가능한 괄호 문자열 -> (...)(...)
• xAy - A는 올바른 암호 문자열, x와 y는 서로 다른 암호 문자. 대응 가능한 괄호 문자열 ((..))

주어진 문자열을 부분 문자열로 분해하여 각각 문제를 해결한 뒤, 부분 문제의 해답에 기반하여 원래 문제의 답을 구할 수 있으므로 DP로 접근할 수 있다.

dp[a][b]를 암호 문자열을 a번째 문자부터 b-1번째 문자까지 사용하였을 때, 만들 수 있는 괄호 문자열의 개수라고 정의하면, 점화식은 아래와 같이 생각해볼 수 있다.

• dp[a][b] = sum(dp[a][k] * dp[k][b]) (a < k < b) + dp[a+1][b-1] (code[a] != code[b]) 

위 점화식에서 "틀렸습니다"를 판정받았다. 케이스를 살펴본 결과 중복 카운팅이 있음을 발견했다.

예를 들어 암호 문자열이 "101010" 인 경우,

• k=2 일때, () + ()() 를 계산
• k=4 일때, ()() + () 를 계산
• 따라서 "()()()"를 중복하여 계산됨

중복 계산을 피하기 위해 문자열을 분해하는 방법을 아래와 같이 재정의 할 수 있다.

• AxBy
  • A와 B모두 올바른 암호 문자열. 빈 문자열일 수 있다
  • x와 y는 서로 다른 암호 문자. 
  • 대응되는 괄호 문자
    • () - A와 B모두 빈 문자열
    • (...)() - B가 빈 문자열
    • ((...)) - A가 빈 문자열
    • (...)((...))

점화식은 아래와 같이 정의할 수 있다.

• dp[a][b] = sum(dp[a][k]  * dp[k + 1][b - 1])) (a <= k < b) (code[k] != code[b-1])

솔루션

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

typedef long long i64;

const int MOD = 1'000'000'007;

i64 dp[301][301];
char code[301];

i64 go(int a, int b) {
    int size = b - a;
    if (size <= 0) return 1;
    if (size % 2) return 0;
    if (size == 2) {
        return code[a] != code[a + 1];
    }
    i64& res = dp[a][b];
    if (res >= 0) return res;
    res = 0;
    for (int i = a; i < b; i += 2) {
        if (code[i] != code[b - 1]) {
            res += go(a, i) * go(i + 1, b - 1) % MOD;
        }
        res %= MOD;
    }
    return res;
}

int main() {
    scanf("%s", code);
    memset(dp, -1, sizeof(dp));
    printf("%lld\n", go(0, strlen(code)));
    return 0;
}