[백준 9252번] LCS 2 (Python3)

import sys
input = sys.stdin.readline
from collections import deque


seq1 = input().strip()
seq2 = input().strip()


l = len(seq2)    
LCS = [0]*l    #seq2 길이의 DP 생성
LCSseq = [""]*l
for letter in seq1:
  MAX = 0
  seq = ""
  for i in range(l):
    if LCS[i] > MAX:
      MAX = LCS[i]
      seq = LCSseq[i]
    else:
      if seq2[i] == letter:
        LCS[i] = MAX+1
        LCSseq[i] = seq+letter

result = [0,""]
for i in range(l):
  if LCS[i]>result[0]:
    result = [LCS[i],LCSseq[i]]

print(result[0])
print(result[1])

 

개인적으로 어려웠던 문제. LCS 1도 어려웠는데 LCS 2도 만만치않았다.

LCS 1의 방식에 추가로 리스트를 하나 더 만들어서 공통된 수열을 저장해놓고 역추적하는것이 중요하다.

 

 

오늘의 교훈) LCS에 대해서 더 자세히 공부하자