BOJ 백준 14505번 팰린드롬 개수 구하기 (Small)

BOJ 백준 14505 팰린드롬 개수 구하기 (Small)

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

14505번: 팰린드롬 개수 구하기 (Small)

 

'BOJ 백준 14517번 팰린드롬 개수 구하기 (Large)'와 동일한 풀이로 해결 가능한 문제여서 BOJ 14517번을 기준으로 풀이했다.

 

 

BOJ 백준 14517 팰린드롬 개수 구하기 (Large)

 

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

14517번: 팰린드롬 개수 구하기 (Large)

 

 

주어진 문자열 S의 부분 수열 중 팰린드롬이 되는 부분수열의 개수를 출력해야 한다. 주의할 점은 문제에서 요구하는 바가 연속된 부분 문자열이 아니라 부분 수열이라는 것이다. 처음에 부분 수열과 부분 문자열을 혼동해서 문제를 잘못 이해했다. 

 

예를 들어, ‘abb’의 부분 문자열은 ‘a’, ‘b’, ‘b’, ‘ab’, ‘bb’, ‘abb’이지만, 부분 수열은 문자열의 각 원소 문자에 대한 부분 집합을 의미한다. 그래서 ‘abb’의 부분 수열은 {'a'}, {'b'}, {'b'}, {'ab'}, {'ab'}, {'bb'}, {'abb’}이다. 이 집합들 중에서 팰린드롬을 만족하는 것들의 개수를 구하는 것이 목표이다. 

 

S의 최대 길이가 1000이므로 문자열의 부분 수열의 최대 개수는 2^1000이 된다. 그래서 모든 부분 수열을 직접 확인하여 팰린드롬의 개수를 구하는 naive한 방식으로는 해결할 수 없다.

 

 

 

Dynamic Programming(다이나믹 프로그래밍) 풀이법으로 이 문제를 접근하고자 다음과 같이 메모이제이션할 배열을 정의헀다.

 

dp[i][j]: i번째 문자에서 j번째 문자까지의 부분 수열 중 팰린드롬의 개수

 

dp[i][j]를 구하려면 크게 두 가지 케이스를 고려할 수 있다.

 

 

 

1) i번째 문자와 j번째 문자가 서로 같은 경우 (s[i] == s[j])

 

dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + 1

 

dp[i][j - 1]와 dp[i + 1][j]를 합하면 교집합인 dp[i + 1][j - 1]이 중복된다. 그러나 i + 1번째 문자에서 j - 1번째 문자까지의 부분 수열에 속하는 팰린드롬, 다시 말해서, dp[i + 1][j - 1]에 속하는 팰린드롬의 왼쪽과 오른쪽 끝에 각각 s[i]와 s[j]를 추가하면 새로운 팰린드롬을 만들 수 있다. 따라서 중복에 대한 제거 처리를 하지 않는다.

 

또한 {s[i], s[j]} 자체의 부분 수열도 팰린드롬에 해당되므로 dp[i][j]에 1을 더한다.

 

 

 

2) i번째 문자와 j번째 문자가 서로 다른 경우 (s[i] != s[j])

 

dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]

 

dp[i][j - 1]와 dp[i + 1][j]를 합하면 교집합인 dp[i + 1][j - 1]이 중복된다. 그래서 포함 배제의 원리에 의해 dp[i + 1][j - 1]를 한 번 빼준다.

 

여기까지는 문자열 S의 길이 제한만 다를 뿐 ‘BOJ 백준 14505번 팰린드롬 개수 구하기 (Small)’와 동일한 문제이다. 그런데 이 문제에서는 구한 값을 10,007로 나눈 나머지를 구해야 하므로 이에 대한 처리가 필요하다.

 

 

 

주의할 점은, dp 배열의 각 원소를 10,007로 나눈 나머지를 가지고 계산할 때 2)번에서 dp[i + 1][j - 1]를 빼 주는 과정에서 음수가 나올 수 있다는 것이다. 따라서 뺄셈에서 음수가 나오지 않도록 나머지를 구하기 전 10,007를 더하는 처리를 요한다.

 

예) 2)번 과정에서

dp[i][j] = ((dp[i][j - 1] % MOD + dp[i + 1][j] % MOD) % MOD + MOD - dp[i + 1][j - 1] % MOD) % MOD

 

 

#include <iostream>
#include <cstring>
#include <string.h>
#include <algorithm>
using namespace std;

const int L_MAX = 1000;
const int MOD = 10007;

string s;
int dp[L_MAX][L_MAX];

int go(int front, int rear){
    if (front > rear){
        return 0;
    }
    if (front == rear){
        return 1;
    }
    
    int& ret = dp[front][rear];
    if (ret != -1){
        return ret;
    }
    
    ret = go(front, rear - 1) % MOD + go(front + 1 ,rear) % MOD;
    ret %= MOD;
    
    if (s[front] == s[rear]){
        ret += 1;
    }
    else {
        ret += MOD;
        ret -= go(front + 1, rear - 1) % MOD;
    }
    
    return ret %= MOD;
}

int main(){
    cin.tie(NULL);
    cin.sync_with_stdio(false);
    
    memset(dp, -1, sizeof(dp));
    
    cin >> s;
    cout << go(0, (int)s.length() - 1) << "\n";
    
    return 0;
}