풀이

1. 문제에 주어진 예시로 한번 직접 LCS를 구해보자.
   
   
2. 다른 예시도 최장 공통 부분 수열을 구해보자.
   
3. 비교하는 두 문자열을 하나씩 추가해보며, 비교해보면 아래의 표와 같다.
   
4. 특히, ACA, CA를 비교하는 상황을 보자. 둘 다 마지막에 A로 끝나는 단어이다. 이는, 마지막 글자는 무조건 같기 때문에 AC와 C 사이의 최장 공통 부분 수열을 계산하면, 마지막에 1만 더하면 된다는 뜻이다.
5. 이를 배열에서 접근하면, DP[i][j]=DP[i-1][j-1]+1이 된다.
6. 하지만, 마지막 글자가 다른 경우엔?
7. 마지막 글자에 도달하기 직전, 두가지 단어의 경우의 수가 있다.
   
   두 가지 경우에서, 가장 긴 경우를 선택하면 된다.

a=' '+input()
b=' '+input()
dp=[[0]*len(b)for _ in range(len(a))]

a와 b 문자열을 입력받고, DP 테이블을 초기화한다.

for i in range(1,len(a)):
    for j in range(1,len(b)):
        if a[i]==b[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])

a[i]==b[i] 마지막 글자가 같은 경우, a와 b의 마지막 글자를 뺀 상황에서 1을 더한 길이와 같다.
a[i]!=b[i] 마지막 글자가 다른 경우, a와 b각각 마지막 글자를 뺀 상황에서 둘 중 더 큰 값과 같다.