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

문제

팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. ‘aba’나 ‘a’와 같은 단어는 팰린드롬이며, ‘abaccbcb’나 ‘anavolimilana’와 같은 단어는 팰린드롬이 아니다.

승수는 주어진 문자열의 부분수열 중 팰린드롬이 되는 부분수열의 개수를 알고싶어한다. (공집합은 포함하지 않는다)

예를들어 ‘abb’ 의 부분수열은 {‘a’}, {‘b’}, {‘b’}, {‘ab’}, {‘ab’}, {‘bb’}, {‘abb’} 이고 이 가운데 팰린드롬은 {‘a’}, {‘b’}, {‘b’}, {‘bb’} 으로 4개 이다. 

문자열이 주어졌을 때, 팰린드롬이 되는 부분수열의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 길이가 1000을 넘지 않는 문자열 S 가 주어진다. 문자열 S는 알파벳 소문자로만 이루어져 있다.

출력

주어진 문자열 S 의 부분수열 중 팰린드롬이 되는 부분수열의 개수를 10,007 로 나눈 나머지를 출력한다.

풀이

$2^{1000}$개를 전부 확인할 수 없으므로 탐색 횟수를 줄이는 것이 목표이다.

팰린드롬은 양 끝에 같은 문자를 붙이면 다시 팰린드롬이 된다. 혹은, 팰린드롬의 양 끝을 잘라내어도 팰린드롬이 된다. 즉, 어떤 구간의 팰린드롬 개수는 그보다 작은 구간의 팰린드롬 개수를 참조하여 구할 수 있다. DP를 이용해 풀 수 있을 것이다.

먼저, 한 글자는 팰린드롬으로 취급한다 하였으므로 base case는 구간의 길이가 1인 것으로 잡을 수 있다.

구간 $S$에 포함되는 팰린드롬은 다음의 경우로 구분할 수 있다.

1. $S$의 양 끝 원소를 모두 포함하는 것
2. $S$의 첫 원소를 포함하지 않는 것
3. $S$의 마지막 원소를 포함하지 않는 것
4. $S$의 양 끝 원소를 모두 포함하지 않는 것

이때 4번은 2번과 3번에 공통적으로 포함되는 경우이므로, 포함-배제 원리를 적용해야 한다.

또한 1번과 4번은 양 끝 원소의 포함 여부 차이이기 때문에, 양 끝 원소 두 개만을 포함한 부분집합 하나를 제외하곤 개수가 같다. 즉, 1번의 개수는 4번의 개수보다 하나 많다.

위의 방법을 통해 S의 부분집합 $2^{1000} \approx 10^{301}$개를 탐색하는 것에서, S의 부분 문자열 ${}_{1000}C_{2} \approx 500,000$개를 탐색하는 것으로 줄일 수 있다.

코드

c++

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

string s;
int dp[1005][1005];

int f(int l, int r){
    if (l > r) return 0;
    if (l == r) return 1;
    if (dp[l][r] == -1) dp[l][r] = (f(l, r - 1) + f(l + 1, r) + (s[l] == s[r] ? 1 : -f(l + 1, r - 1)) + 10007) % 10007;
    return dp[l][r];
}

int main(){
    cin >> s;
    memset(dp, -1, sizeof(dp));
    cout << f(0, s.length() - 1);
}

python

def f(l, r):
    if l > r: return 0
    if l == r: return 1
    if dp[l][r] == -1: dp[l][r] = (f(l + 1, r) + f(l, r - 1) + (1 if s[l] == s[r] else -f(l + 1, r - 1))) % 10007
    return dp[l][r]
s = input()
dp = [[-1] * 1005 for _ in range(1005)]
print(f(0, len(s) - 1))