9252. LCS 2

업데이트 시간 : 2023-07-26 10:19:16 +0000

[Gold IV] LCS 2 - 9252

문제 링크

성능 요약

메모리: 426800 KB, 시간: 664 ms

분류

다이나믹 프로그래밍

문제 설명

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

💡 Solutions

📄 LCS 2.py

import sys
# https://www.acmicpc.net/problem/9252

text1 = [''] + list(sys.stdin.readline().rstrip())
text2 = [''] + list(sys.stdin.readline().rstrip())

l1 = len(text1)
l2 = len(text2)

LCS = [['']*l2 for _ in range(l1)]

for i in range(1,l1):
    for j in range(1,l2):
        if text1[i] == text2[j]:
            LCS[i][j] = LCS[i-1][j-1] + text1[i]
        else:
            if len(LCS[i-1][j]) > len(LCS[i][j-1]):
                LCS[i][j] = LCS[i-1][j]
            else:
                LCS[i][j] = LCS[i][j-1]
result = LCS[-1][-1]
print(len(result))
print(result)