코드
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int dp[1003][1003];
string a, b;
int main() {
cin >> a;
cin >> b;
for (int i = 1; i < a.size() + 1; i++) {
for (int j = 1; j < b.size() + 1; j++) {
if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
cout << dp[a.size()][b.size()] << '\n';
return 0;
}풀이
dp배열의 정의는 문자열 a의 처음 i개의 문자와 문자열 b의 처음 j개의 문자 사이에서 최장 공통 부분 수열의 길이를 의미한다. 두 문자가 일치하는 경우 (a[i - 1] == b[j - 1])에 공통 부분 수열의 길이는 이전까지의 길이에 1을 더해준 값이 된다. 따라서 dp[i][j] = dp[i - 1][j - 1] + 1가 된다. 두 문자가 일치하지 않는 경우에는 공통 부분 수열에 포함되지 않으므로, 최장 공통 부분 수열의 길이는 이전 상태 중 최댓값을 그대로 사용하게 된다. 따라서 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])가 된다. 여기서 dp[i][j - 1]은 문자열 b의 마지막 문자를 제외한 경우의 LCS 길이를 의미하고 dp[i - 1][j]는 문자열 a의 마지막 문자를 제외한 경우의 LCS 길이를 의미한다.
아래 블로그에 LCS 원리가 잘 정리 되어 있다.
'백준' 카테고리의 다른 글
| [백준] 1504번 특정한 최단 경로 C++코드 (0) | 2024.10.10 |
|---|---|
| [백준] 14500번 테트로미노 C++ 코드 (0) | 2024.10.10 |
| [백준] 2638번 치즈 C++ 코드 (0) | 2024.10.10 |
| [백준] 1074번 Z C++ 코드 (0) | 2024.10.10 |
| [백준] 16953번 A → B C++ 코드 (0) | 2024.10.07 |
