동적 프로그래밍을 활용한 최장 공통 부분 수열 구하기 문제이다. 사실 이 문제는 LCS 알고리즘으로 많이 알려져있는 문제이다. 그렇기에 어렵지않게 풀 수 있었다.
문자열의 크기만큼 반복문을 돌면서 같은 문자열을 발견하게 되면, 해당 위치의 LCS 배열에서 + 1한 값을 LCS[i + 1][j+ 1]
에 저장해준다. 이렇게하는 이유는 위 표와 같이 문자열 앞에 0을 더해주지 않았기때문에 한칸씩 옮겨서 저장을 해주었다. 같은 문자열이 아니라면 왼쪽, 위쪽중에 큰 값을 LCS[i + 1][j + 1]
에 저장해준다. 결국 마지막에는 LCS 최종 값이 저장되어 있게 된다. 이 문제는 어렵지 않게 풀었기에 문제가 없었다.
#include <iostream>
#include <algorithm>
using namespace std;
string A, B;
int LCS[1001][1001];
void solution() {
for (int i = 0; i < A.size(); i++) {
for (int j = 0; j < B.size(); j++) {
if (A[i] == B[j]) {
LCS[i + 1][j + 1] = LCS[i][j] + 1;
}
else {
LCS[i + 1][j + 1] = max(LCS[i][j + 1], LCS[i + 1][j]);
}
}
}
cout << LCS[A.size()][B.size()];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> A;
cin >> B;
solution();
return 0;
}