※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
LCS는 Longest Common Subsequence 의 약자로, 최장 공통 부분 수열을 뜻합니다. 예를들어 ABCD 와 ACD의 LCS는 ACD가 됩니다. 이러한 형태의 LCS는 동적 프로그래밍을 입문할 때 대표격으로 풀어볼 수 있는 문제입니다.
두 개의 문자열 $S$, $T$에 대해 다음과 같은 식이 성립합니다.
$dp[i][j] =\begin{cases}dp[i-1][j-1]+1, & \text{S[i]==T[j]} \\max(dp[i-1][j],dp[i][j-1]) & \text{S[i]!=T[j]}\end{cases}$
위의 식은 무슨 뜻일까요? S 문자열의 i번째와, T문자열의 j번째 문자열이 같다면, LCS의 값이 1 증가한다는 뜻이 됩니다. 그 때, 이 문자열을 검사하기 직전의 위치가 S 문자열의 i-1번째와 T문자열의 j-1번째 이므로 이 위치에서 1을 더해주게 됩니다.
만약 같지 않다면, S 문자열에서 하나를 넘겨 검사하거나, T문자열에서 하나를 넘겨 검사해야 할 것입니다. 그리고 그 중, 더 큰 값을 취하면 됩니다. 이 문제를 처음 풀어보시는 분은 적당한 길이의 문자열을 예제로 두고, 손으로 직접 칸을 채워가시면서 풀어보시는 것도 이해에 많은 도움이 됩니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string a,b;
int c,d,e[1000][1000]={0};
int main()
{
cin>>a>>b;
c=a.length(),d=b.length();
for(int i=1;i<=c;i++)
for(int j=1;j<=d;j++)
if(a[i-1]==b[j-1])e[i][j]=e[i-1][j-1]+1;
else e[i][j]=max(e[i-1][j],e[i][j-1]);
cout<<e[c][d];
}