# 9252. LCS 2 [링크](https://www.acmicpc.net/problem/9252) | 난이도 | 정답률(\_%) | | :----: | :---------: | |Gold V|42.193| ## 설계 ### 동적 계획법 ## 정리 | 내 코드 (ms) | 빠른 코드 (ms) | | :----------: | :------------: | |652| | ## 고생한 점 ## 코드 ```cpp #include <algorithm> #include <iostream> #include <string> #include <vector> #define MAXSIZE 1001 #define nl "\n" using namespace std; int DP[MAXSIZE][MAXSIZE]; string LCS[MAXSIZE][MAXSIZE]; void solution() { string A, B; cin >> A >> B; int A_Size = A.length(); int B_Size = B.length(); for (int i = 1; i <= A_Size; i++) { for (int j = 1; j <= B_Size; j++) { if (A[i - 1] == B[j - 1]) { DP[i][j] = DP[i - 1][j - 1] + 1; LCS[i][j] = LCS[i][j] + LCS[i - 1][j - 1] + A[i - 1]; } else { DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]); if (LCS[i - 1][j].length() > LCS[i][j - 1].length()) { LCS[i][j] = LCS[i - 1][j]; } else { LCS[i][j] = LCS[i][j - 1]; } } } } cout << DP[A_Size][B_Size] << nl << LCS[A_Size][B_Size] << nl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solution(); return 0; } ```
Activity