백준 9252번 C++

#include <iostream>

#include <string>

#include <algorithm>

#include <cstring>

using namespace std;

const int MAX = 1001;

string s1, s2;

int cache[MAX][MAX];

string ansstring;

int LIS(int i, int j) {

if (i == s1.size() || j == s2.size())

return 0;

int &answer = cache[i][j];

if (cache[i][j] != -1)

return cache[i][j];

return answer = max(LIS(i + 1, j), max(LIS(i, j + 1), LIS(i + 1, j + 1) + (s1[i] == s2[j])));

}

void calstring(int i, int j) {

if (i == s1.size() || j == s2.size())

return;

if (s1[i] == s2[j]) {

ansstring += s1[i];

calstring(i + 1, j + 1);

}

else if (cache[i + 1][j] >= cache[i][j+1])

calstring(i + 1, j);

else

calstring(i, j + 1);

}

int main(void) {

cin >> s1 >> s2;

memset(cache, -1, sizeof(cache));

cout << LIS(0, 0) << endl;

calstring(0, 0);

cout << ansstring << endl;

return 0;

}