[BAEKJOON] 9592 LCS2

#include <iostream> #include <string> #include <vector> using namespace std; int main() { vector<vector<string>> dp = vector<vector<string>>(2, vector<string>(10001, "")); string a, b, ans=""; cin >> a >> b; int alen = a.length(), blen = b.length(); for (int y = 1; y <= blen; y++) { for (int x = 1; x <= alen; x++) { if (a[x - 1] == b[y - 1]) dp[y % 2][x] = dp[(y - 1) % 2][x - 1] + a[x - 1]; else { if (dp[(y - 1) % 2][x].length() > dp[y % 2][x - 1].length()) dp[y % 2][x] = dp[(y - 1) % 2][x]; else dp[y % 2][x] = dp[y % 2][x - 1]; } if (ans.length() < dp[y % 2][x].length()) ans = dp[y % 2][x]; } } cout << ans.length() << endl; cout << ans << endl; return 0; }

9591 LCS를 이용해서 풀었다.