LCS 2 9252

문제

접근 방법

LCS는 값이 같을 경우 대각선에서 값을 가져와서 1 더해주면 된다. (왼쪽, 오른쪽의 값을 가져오면 AAA, AAA의 경우 하나의 A로 3개가 충족되는 상황이 만들어진다)
즉 공통부분 수열의 값이 올라가는 부분은 대각선이다.
대각선으로 값이 오르는 부분을 찾아내면 LCS를 찾아낼 수 있을 것이다.

코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;
string A, B;
vector<vector<int>> dp;
int aSize, bSize;
// 값이 오른 부분 추적
void recur(int y, int x)
{
    if (x == 0 || y == 0) // 끝에 도달한 경우
        return;
    if (dp[y][x] == dp[y - 1][x - 1] + 1 && dp[y][x] == dp[y - 1][x] + 1 && dp[y][x] == dp[y][x - 1] + 1) // 오른쪽, 왼쪽 값 가져온 경우 제외
    {
        recur(y - 1, x - 1);
        cout << A[y - 1];
    }
    else
    {
        if (dp[y][x - 1] > dp[y - 1][x]) // 이어온 값을 추적
            recur(y, x - 1);
        else
            recur(y - 1, x);
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> A >> B;
    aSize = A.size(), bSize = B.size();
    dp = vector<vector<int>>(aSize + 1, vector<int>(bSize + 1));
    for (int i = 1; i <= aSize; ++i)
        for (int j = 1; j <= bSize; ++j)
            if (A[i - 1] == B[j - 1]) // 같다면 대각선에서 가져오기
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
    cout << dp[aSize][bSize] << "\n";
    recur(aSize, bSize);
    return 0;
}

풀이

LCS에서 문자열이 무엇인지도 출력하게 변형된 문제이다.
역추적할 때 x 또는 y가 0이면 끝에 도달한 것이기에 반환하면 된다.