Boj 9252 c++ LCS 2

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

 

#9251에서 LCS 문자열을 출력하는 것이 추가된 문제이다.

 

이를 위해서는 동적계획법 역추적을 해야 한다.

Parent 배열에는 해당 LCS를 찾은 경로를 저장한다. (i-1, j-1)      또는     (i, j-1)      또는     (i-1, j)

 

 

LCS는 두 문자열을 순차적으로 비교하였을 때 일피하는 순간 성립하므로 (i-1, j-1) 이 저장된 Parent 인덱스의 문자만 LCS에 추가하는 것이 기본 논리이다.

 

이렇게 Parent 배열에 값이 더이상 남아있지 않을 때까지 역추적을 하여 생성한 문자열은 원래의 문자열에서 뒤집어져있기에 

이를 다시 역순으로 정렬하여 출력하면 된다.

 

정답 코드

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

int dp[1001][1001]; //i, j번째 문자열까지 고려하였을 때 LCS의 길이
char Parent[1001][1001]; //u = -1-1, r = 0 -1, l = -1 0

int main() {

    int n, m;

    string s1, s2;
    cin >> s1 >> s2;
    n = s1.length();
    m = s2.length();

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(s1[i] == s2[j]) {
                dp[i+1][j+1] = dp[i][j] + 1;
                Parent[i+1][j+1] = 'u';
            }
            else if(dp[i+1][j] >= dp[i][j+1]){
                dp[i+1][j+1] = dp[i+1][j];
                Parent[i+1][j+1] = 'r';
            }
            else{
                dp[i+1][j+1] = dp[i][j+1];
                Parent[i+1][j+1] = 'l';
            }
        }
    }

    cout << dp[n][m] << "\n";

    string ans = "";

    while(Parent[n][m] != NULL){
        if(Parent[n][m] == 'u'){
            ans.push_back(s1[n-1]); // 인덱스 보정
            n--;
            m--;
        }
        else if(Parent[n][m] == 'r'){
            m--;
        }
        else if(Parent[n][m] == 'l'){
            n--;
        }
    }

    reverse(ans.begin(), ans.end());
    cout << ans;

}