백준 1054번 팰린드롬 문장

문제 링크

자력솔이다. 예전에 한 번 보고 “아, 비트DP구나”만 생각하고 묵혀놨던 문제다.

어떤 단어를 회문의 중심으로 잡고, 왼쪽과 오른쪽에 단어를 추가하며 비트DP를 할 것이다. 중심을 기준으로 왼쪽 문자열을 $L$, 오른쪽 문자열을 $R$라고 하자. $n(L) \lt n(R)$라면 $L$에 단어를 추가하고, 아니라면 $R$에 단어를 추가할 것이다. 단어를 추가한다면, 반대쪽 문자열과 대응되는지를 확인하고 추가해야 한다. 이때 양쪽 문자열 중 길이가 더 긴 문자열이 중요함을 알 수 있다.

이제 DP식을 정의하면 다음과 같다:

\[DP[bit][i][j][d] = \text{변수의 정의가 아래와 같을 때 단어를 추가하여 회문을 만들 수 있는 경우의 수}\]

• $bit$ : 사용한 단어의 집합 (비트마스트)
• $d \in {L, R}$ 문자열이 $j$만큼 더 길다.
• $d$에 끝에 $i$번 단어가 있다.

단어를 추가할 때 2 경우로 나눌 수 있다.

1. 추가한 단어가 완전히 대응됨.
2. 추가한 단어가 완전히 대응되지 않음.

1번 경우를 만족하는 문자열의 집합을 $P$, 2번 경우를 만족하는 문자열의 집합을 $Q$라고 한다면 DP식은 다음과 같다.

\(DP[bit][i][0][d] = \sum_{x \in bit^c}DP[bit \cup x][x][n(x)][L] + 1\) \(DP[bit][i][j][d] = \sum_{x \in P}DP[bit \cup x][i][j-n(x)][d] + \sum_{x \in Q}DP[bit \cup x][x][n(x)-j][\{L, R\} \setminus \{d\}]\)

배열의 크기를 1 작게 잡아서 1틀 했다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int MAXN = 13;

int N;
string s[MAXN];
ll cache[1<<MAXN][MAXN+1][MAXN+1][2];

bool checkin(const string& a, const string& b, int i, int left)
{
    int n = a.size();
    int m = b.size();
    if(b.size() > i) return false;
    if(left) {
        auto s = a.substr(0, i);
        s = s.substr(s.size() - m);
        reverse(s.begin(), s.end());
        return s == b;
    } else {
        auto s = a.substr(n-i);
        s = s.substr(0, m);
        reverse(s.begin(), s.end());
        return s == b;
    }
}
bool checkextend(const string& a, const string& b, int i, int left)
{
    int n = a.size();
    int m = b.size();
    if(b.size() <= i) return false;
    if(left) {
        auto s = a.substr(0, i);
        auto ss = b.substr(0, i);
        reverse(s.begin(), s.end());
        return s == ss;
    } else {
        auto s = a.substr(n-i);
        auto ss = b.substr(m-i);
        reverse(s.begin(), s.end());
        return s == ss;
    }
}

ll dp(int taken, int i, int j, int left)
{
    ll& ret = cache[taken][i][j][left];
    if(ret != -1) return ret;
    ret = 0;
    if(j == 0) {
        ret = 1;
        for(int k = 0; k < N; k++) {
            if(taken&(1<<k)) continue;
            ret += dp(taken|(1<<k), k, s[k].size(), 0);
        }
        return ret;
    }
    int m = s[i].size();
    for(int k = 0; k < N; k++) {
        if(taken&(1<<k)) continue;
        int m = s[k].size();
        if(checkin(s[i], s[k], j, left)) ret += dp(taken|(1<<k), i, j-m, left);
        if(checkextend(s[i], s[k], j, left)) ret += dp(taken|(1<<k), k, m-j, !left);
    }
    return ret;
}

int main()
{
    memset(cache, -1, sizeof(cache));
    cin >> N;
    for(int i = 0; i < N; i++) cin >> s[i];

    ll ans = 0;

    for(int i = 0; i < N; i++) {
        int n = s[i].size();
        for(int j = 0; j < n; j++) {
            int c = -1;
            int l = j;
            int r = j;
            bool possible = true;
            while(l >= 0 && r < n) {
                if(s[i][l] != s[i][r]) {
                    possible = false;
                    break;
                }
                c += 2;
                l--; r++;
            }
            if(possible) ans += dp(1<<i, i, n-c, l >= 0);
        }
        for(int j = 0; j < n; j++) {
            int c = 0;
            int l = j-1;
            int r = j;
            bool possible = true;
            while(l >= 0 && r < n) {
                if(s[i][l] != s[i][r]) {
                    possible = false;
                    break;
                }
                c += 2;
                l--; r++;
            }
            if(possible) ans += dp(1<<i, i, n-c, l >= 0);
        }
    }

    cout << ans;
}