이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. dp리스트를 a, b 두 수열의 길이로 된 2차원 리스트로 선언하고, 2중 for문을 통해 a, b를 순회하며 만약 a[i]와 b[j]가 같을 경우에는 dp[i][j]를 dp[i-1][j-1]+a[i]로 갱신해주고, 같지 않다면 dp[i][j]를 dp[i-1][j]와 dp[i][j-1] 중 길이가 더 긴 값으로 갱신해주었다. 점화식은 다음과 같다.

dp[i][j] = dp[i-1][j-1]+a[i] (a[i]==b[j])

Code

a = [''] + list(str(input()))
b = [''] + list(str(input()))
dp = [['' for _ in range(len(b))] for _ in range(len(a))]
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]+a[i]
        else:
            if len(dp[i-1][j]) > len(dp[i][j-1]):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
print(len(dp[len(a)-1][len(b)-1]))
print(dp[len(a)-1][len(b)-1])