[BOJ] 13841 It Prefokery Pio

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

13841번: It Prefokery Pio

이 문제는 어떤 문자열이 주어졌을 때, 해당 문자열로 만들 수 있는 가장 긴 palindorme을 구하는 문제이다.

문자열과 해당 문자열의 거꾸로 입력한 문자열을 비교하여 LCS를 구하면 해결 할 수 있다.

 

#include <iostream>
#include <string>
using namespace std;

int LCS[2001][2001];
int path[2001][2001];
//path -1 from left, 0 from top, 1 from diagonal line
string input;
string output;

void find_palindrome(){
    string reverse;
    for(int i=input.size()-1;i>=0;i--) reverse.push_back(input[i]);
    for(int i=0;i<=input.size();i++) LCS[i][0]=0;
    for(int i=0;i<=input.size();i++) LCS[0][i]=0;
    
    for(int i=1;i<=input.size();i++){
        for(int j=1;j<=input.size();j++){
            if(input[i-1]==reverse[j-1]){
                LCS[i][j]=LCS[i-1][j-1]+1;
                path[i][j]=1;
            }else{
                if(LCS[i-1][j]>LCS[i][j-1]){
                    LCS[i][j]=LCS[i-1][j];
                    path[i][j]=0;
                }else{
                    LCS[i][j]=LCS[i][j-1];
                    path[i][j]=-1;
                }
            }
        }
    }
    int cnt=0;
    int x=reverse.size();
    int y=input.size();
    int size=LCS[y][x];
    while(cnt!=size){
        if(path[y][x]==1){
            output.push_back(input[y-1]);
            cnt++;y--;x--;
        }else{
            if(path[y][x]==0) y--;
            else x--;
        }
    }
    
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    while(getline(cin,input)){
        output.clear();
        find_palindrome();
        cout<<output<<'\n';
    }
    return 0;
}