์๊ณ ๋ฆฌ์ฆ
LCS ์๊ณ ๋ฆฌ์ฆ์ ๊ต์ฅํ ์ ์ค๋ช ํ ๊ธ์ด ์์ด ๋งํฌ๋ก ๋์ฒด
์ฝ๋
#include <iostream>
using namespace std;
string s[2];
int map[1011][1011];
int max(int a, int b) {
return a < b ? b : a;
}
int main() {
cin >> s[0] >> s[1];
for (int i = 1; i <= s[1].size(); i++) {
for (int j = 1; j <= s[0].size(); j++) {
if (s[1][i - 1] == s[0][j - 1])
map[i][j] = map[i - 1][j - 1] + 1;
else
map[i][j] = max(map[i - 1][j], map[i][j - 1]);
}
}
cout << map[s[1].size()][s[0].size() ];
}