[Gold IV]
https://www.acmicpc.net/problem/9252
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
참고
[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence
풀이
0 - 1 Knapsack 문제와 비슷하게 2차원 배열을 이용한 DP로 풀이할 수 있는 LCS(Longest Common Subsequence, 최장 공통 부분수열) 문제.
최장 공통 문자열 문제와 유사하지만, 조금 다른 풀이.
문제를 보고 혼자 생각해내기는 쉽지 않으니 미리 익혀두자 '^'
from collections import deque
str1 = input()
str2 = input()
dp = [[0 for _ in range(len(str1)+1)] for _ in range(len(str2)+1)]
for i in range(1, len(str2)+1):
for j in range(1, len(str1)+1):
if str2[i-1] == str1[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
result = deque([])
i = len(str2)
j = len(str1)
while dp[i][j] != 0:
if dp[i][j] == dp[i][j-1]:
j -= 1
elif dp[i][j] == dp[i-1][j]:
i -= 1
else:
result.appendleft(str2[i-1])
i -= 1
j -= 1
print(len(result))
print(*result, sep="")