BOJ 9252번 LCS2

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

github : https://github.com/junho0956/Algorithm/blob/master/9252/9252/%EC%86%8C%EC%8A%A4.cpp

 

LCS 기본개념

LCS : https://junho0956.tistory.com/39?category=868069

 

LCS 의 스트링을 알기위해서는 DP 가 값이 채워지는 형태를 관찰하시면 됩니다.

if( str1[i] == str2[k] ) 이 되는 지점에서 i-1, k-1 에서 +1 값을 하는 형태입니다.

 

DP 의 형태를 자세히 관찰해보면 같은 값을 이루는 형태가

 

00000000

01111111

01111222

01222233

01222234

01222234

 

이런식으로 이루어지게 될것입니다.

여기서 알 수 있는 것은 값이 i-1, k-1 에서 +1 했을 때 바뀌는 지점은 분명 공통으로 단어를 가지고있는 부분이 된다는 뜻이고, 위의 숫자의 배열들을 봤을 때 그 특정 지점을 알기 위해서는 자신을 기준 i-1 또는 k-1 한 부분이 같은 값이면

어디에서 값이 바뀐 것인지 알 수 없기 때문에 그 같은 지점으로 이동하면서 탐색을 해주면 되는 것입니다.

i-1, k-1 둘다 값이 다른 값이 +1로 갱신되는 지점이 LCS를 만족하는 부분이 되기 때문에 그 부분을 스택에 넣어두셨다가 마지막에 출력해주시면 됩니다.

#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;
 
int dp[1001][1001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    string str1, str2;
    cin >> str1 >> str2;
 
    for (int i = 0; i < str1.length(); i++) {
        for (int k = 0; k < str2.length(); k++) {
            if (str1[i] == str2[k]) dp[i + 1][k + 1] = dp[i][k] + 1;
            else dp[i + 1][k + 1] = max(dp[i + 1][k], dp[i][k + 1]);
        }
    }
 
    cout << dp[str1.length()][str2.length()] << "\n";
 
    // backtracking
    // dp가 덮히는 특성상 끝지점을 기준 위->왼쪽로 가면서 스트링 길이에 맞게 계속 이동한다
 
    stack<char> s;
    int cnt = dp[str1.length()][str2.length()];
    int y = str1.length();
    int x = str2.length();
    while (cnt) {
        // 현재 dp값이 cnt와 같을때 왼쪽과 위를 확인
        if (dp[y][x] == cnt) {
            if (dp[y][x - 1] == cnt) x--;
            else if (dp[y - 1][x] == cnt) y--;
            // 같다면 위로 한칸 이동한다
            else s.push(str1[y - 1]), y--, cnt--;
        }
    }
 
    while (!s.empty()) {
        cout << s.top();
        s.pop();
    }
 
    return 0;
}