baekjun 9252. LCS2

 Longest Common Sequence 메트릭스를 만들고 역으로 올라가서 LCS 문자열을 구하는 문제

#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
int strBoard[1001][1001];
string s1;
string s2;
string getLCS(int i, int j) {
    if (strBoard[i][j] == 0)
        return "";
    while (strBoard[i][j] == strBoard[i - 1][j])
        i--;
    while (strBoard[i][j] == strBoard[i][j - 1])
        j--;
    return getLCS(i - 1, j - 1) + s1[i - 1];
}
 
int main() {
    cin >> s1 >> s2;
    int lenS1 = (signed)s1.size();
    int lenS2 = (signed)s2.size();
    for (int i = 1; i <= lenS1; i++) 
        for (int j = 1; j <= lenS2; j++) 
            if (s1[i - 1] == s2[j - 1])
                strBoard[i][j] = strBoard[i - 1][j - 1] + 1;
            else if(s1[i - 1] != s2[j - 1])
                strBoard[i][j] = max(strBoard[i][j - 1], strBoard[i - 1][j]);
    
    cout << strBoard[lenS1][lenS2] << endl;
    cout << getLCS(lenS1, lenS2) << endl;
    //system("pause");
    return 0;
}