[DP] LCS

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

using namespace std;

void Lcs(const string& X, const string& Y)
{
    int N = X.size();
    int M = Y.size();

    vector< vector<int> > DP(N + 1, vector<int>(M + 1, 0));

    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= M; ++j)
        {
            if ( X[i - 1] == Y[j - 1] )
            {
                DP[i][j] = DP[i - 1][j - 1] + 1;
            }
            else
            {
                DP[i][j] = max( DP[i - 1][j], DP[i][j - 1] );
            }
        }
    }
    
    string lcs = "";
    int i = N, j = M;
    while ( i > 0 && j > 0)
    {
        if ( X[i - 1] == Y[j - 1] )
        {
            lcs += X[i - 1];
            --i;
            --j;
        }
        else if( DP[i - 1][j] > DP[i][j - 1] )
        {
            --i;
        }
        else
        {
            --j;
        }
    }
    
    reverse(lcs.begin(), lcs.end());

    cout << DP[N][M] << '\n' << lcs;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string Str1, Str2;

    cin >> Str1 >> Str2;

    Lcs( Str1, Str2 );
}

i는 X의 i번째 까지 고려한다

j는 Y의 j번째 까지 고려한다

 

같은 경우

- DP[i - 1][j - 1] => 이 전까지 고려되었던 가장 긴 공통 부분

다른 경우

- 둘 중 하나는 무시하고 진행