[백준 9252] LCS 2 (DP) (C/C++) (★★★)

#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
 
string A, B;
int dp[1010][1010];
string result;
 
int solve(int aIdx, int bIdx)
{
    if(aIdx == A.size() || bIdx == B.size())
    {
        return 0;
    }
    
    if(dp[aIdx][bIdx] != 0)
    {
        return dp[aIdx][bIdx];
    }
    
    if(A[aIdx] == B[bIdx])
    {
        dp[aIdx][bIdx] = solve(aIdx+1, bIdx+1) + 1;
    }
    else
    {
        dp[aIdx][bIdx] = max(solve(aIdx+1, bIdx), solve(aIdx, bIdx+1));
    }
    
    return dp[aIdx][bIdx];
}
 
int main(void)
{
//    freopen("B9252_input.txt", "r", stdin);
    
    cin >> A >> B;
    
    cout << solve(0, 0) << endl;
 
    int aIdx = 0;
    int bIdx = 0;
    while(dp[aIdx][bIdx] != 0)
    {
        if(dp[aIdx][bIdx] == dp[aIdx+1][bIdx])
        {
            aIdx++;
        }
        else if(dp[aIdx][bIdx] == dp[aIdx][bIdx+1])
        {
            bIdx++;
        }
        else if(dp[aIdx][bIdx]-1 == dp[aIdx+1][bIdx+1])
        {
            result += A[aIdx];
            aIdx++;
            bIdx++;
        }
    }
    
    cout << result << endl;
    
    return 0;
}