[BAEKJOON] 9251 LCS

#include <string> #include <algorithm> #include <iostream> using namespace std; int dp[1001][1001]; int main() { string a, b; cin >> a >> b; int al_en = a.length(); int b_len = b.length(); for (int i = 0; i < al_en ; ++i) { for (int j = 0; j < b_len ; ++j) { if (a[i] == b[j]) dp[i + 1][j + 1] = dp[i][j] + 1; else dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]); } } cout << dp[al_en][b_len] << endl; return 0; }

LCS를 몰라서 찾아보았다

음..찾아도 모르겠는데

2차원 배열을 만들어서 두개의 string 을 비교하는데

같은 게 있으면 대각선 전에서 1을 더하고

아니면 오른쪽과 아래를 비교하여 max 값을 저장한다

조금만 더 찾아봐야겠다...