BOJ 백준 13841 : It Prefokery Pio

시작하면서

　이번 문제는 가장 긴 팰린드롭 부분 문자열(Longest Palindromic Subsequence) 문제이다.

BOJ 13841 - It Prefokery Pio

​

문제 이해

​ 해당 문제는 가장 긴 팰린드롭 부분 문자열 개념을 적용하기만 하면 되는 문제이다. 아래 링크에 개념 정리를 해두었으니 보고 풀기를 추천한다.

LINK

​

해결

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

/*
    reference : https://www.techiedelight.com/longest-palindromic-subsequence-using-dynamic-programming/
*/

// Function to find length of LCS of substring X[0..n-1] and Y[0..n-1]
int GetLongestPalindromeSubsequenceLength(string X, string Y, vector<vector<int>> &lookup, int n)
{
    for (int i = 0; i < lookup.size(); i++)
    {
        for (int j = 0; j < lookup[i].size(); j++)
        {
            lookup[i][j] = 0;
        }
    }

    // fill the lookup table in bottom-up manner
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            // if current character of X and Y matches
            if (X[i - 1] == Y[j - 1])
            {
                lookup[i][j] = lookup[i - 1][j - 1] + 1;
            }
            // else if current character of X and Y don't match
            else
            {
                lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1]);
            }
        }
    }

    return lookup[n][n];
}

// Function to find LCS of string X[0..m-1] and Y[0..n-1]
string GetLongestPalindromeSubsequenceString(string X, string Y, vector<vector<int>> &lookup, int m, int n)
{
    // return empty stirng if we have reached the end of
    // either sequence
    if (m == 0 || n == 0)
        return string("");

    // if last character of X and Y matches
    if (X[m - 1] == Y[n - 1])
    {
        // append current character (X[m-1] or Y[n-1]) to LCS of
        // substring X[0..m-2] and Y[0..n-2]
        return GetLongestPalindromeSubsequenceString(X, Y, lookup, m - 1, n - 1) + X[m - 1];
    }

    // else when the last character of X and Y are different

    // if top cell of current cell has more value than the left cell,
    // then drop current charcter of string X and find LCS of substring X[0..m-2], Y[0..n-1]

    if (lookup[m - 1][n] > lookup[m][n - 1])
        return GetLongestPalindromeSubsequenceString(X, Y, lookup, m - 1, n);

    // if left cell of current cell has more value than the top cell,
    // then drop current character of string Y and find LCS of substring X[0..m-1], Y[0..n-2]

    return GetLongestPalindromeSubsequenceString(X, Y, lookup, m, n - 1);
}

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // sync off

    vector<vector<int>> lookup;
    string X, Y;

    lookup.resize(2001);
    for (int i = 0; i < lookup.size(); i++)
    {
        lookup[i].resize(2001, 0);
    }

    while (cin >> X)
    {
        Y = X;
        reverse(Y.begin(), Y.end());

        GetLongestPalindromeSubsequenceLength(X, Y, lookup, X.length());
        cout << GetLongestPalindromeSubsequenceString(X, Y, lookup, X.length(), X.length()) << "\n";
    }

    return 0;
}