[백준] 9252. LCS 2 - 파이썬

[Gold IV]

 

https://www.acmicpc.net/problem/9252

9252번: LCS 2

 

참고

[알고리즘] 그림으로 알아보는 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="")