[BAE/<JOON> 문제풀이] 9252. LCS2 (DP.042)

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

9252번: LCS 2

기존 LCS를 추적해서 문자열을 뽑아내는 부분이 추가된 문제다.

 

공통부분문자열 알고리즘은 그대로 적용하고 최댓값을 탐색하기 위해서 사용했던 테이블을 그대로 복기하며 문자열을 뽑아주면 된다.

 

우선 최댓값이 들어간 위치를 미리 저장해놓고, 그 위치부터 역순으로 배열을 탐색하며 이전 길이의 문자열에서의 갱신이 몇번째 문자에서 이루어졌는지 짚어가며 출력한다.

 

mi, mj = 최댓값이 저장되어있는 위치
s1, s2 = 문자열

stack<char> dap;    
for (int i = mi; i >= 1; i--) {
        if (mj == 1) break;        
        int current = dp[i][mj];
        for (int j = mj; j >= 1; j--) {
        //이전 문자를 썼을 때 LCS최대길이 : dp[i-1][j], dp[i][j-1] 보다 크다면 갱신이 이루어진것임
            if (dp[i][j] > dp[i][j - 1] && dp[i][j] > dp[i - 1][j] && dp[i][j] == current) {
                dap.push(s2[j - 1]); //해당 문자 저장
                mj = j;
                break;
            }
        }
    }

이후 저장한 문자들을 출력해주면 된다.

 

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

using namespace std;

int main()
{
    string s1;
    string s2;
    cin >> s2 >> s1;
    int l1 = s1.length();
    int l2 = s2.length();
    vector<vector<int>> dp;
    dp.resize(l1 + 1);
    dp[0].resize(l2 + 1);    
    int mi = -1, mj = -1;
    int mx = 0;
    for (int i = 1; i <= l1; i++) {
        dp[i].resize(l2 + 1);        
        for (int j = 1; j <= l2; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + 1);                                
                if (mx < dp[i][j]) {
                    mx = dp[i][j];
                    mi = i;
                    mj = j;
                }
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
            //cout << dp[i][j] << " ";
        }
        //cout << "\n";
    }    
    cout << mx << "\n";        
    stack<char> dap;    
    for (int i = mi; i >= 1; i--) {
        if (mj == 1) break;        
        int current = dp[i][mj];
        for (int j = mj; j >= 1; j--) {
            if (dp[i][j] != dp[i][j - 1] && dp[i][j] != dp[i - 1][j] && dp[i][j] == current) {
                dap.push(s2[j - 1]);
                mj = j;
                break;
            }
        }
    }

    while (!dap.empty()) {
        cout << dap.top();
        dap.pop();
    }
    
    return 0;
}