[백준][9252][Python 파이썬][G4] LCS 2

 

문제

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

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

입력

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

출력

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

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

 

테스트케이스

ACAYKP CAPCAK	KKKBCBCAAA KCKBCBCAKK	AAAA AAA	ABCDEF BEFDEFACDFABZ
4 ACAK	7 KKBCBCA	3 AAA	4 BDEF

 

코드

import sys

input = sys.stdin.readline

stra = input().rstrip()

strb = input().rstrip()

alen = len(stra)

blen = len(strb)

dp = [[0 for i in range(alen)] for j in range(blen)]

if stra[0] == strb[0]:

    dp[0][0] = 1

for i in range(1, alen):

    if dp[0][i-1] == 1:

        dp[0][i] = 1

    elif strb[0] == stra[i]:

        dp[0][i] = 1

for i in range(1, blen):

    if dp[i-1][0] == 1:

        dp[i][0] = 1

    elif stra[0] == strb[i]:

        dp[i][0] = 1

for i in range(1, blen):

    for j in range(1, alen):

        if stra[j] == strb[i]:

            dp[i][j] = max(dp[i][j-1], dp[i-1][j-1]+1)

        else:

            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

ans = dp[blen-1][alen-1]

print(ans)

x = blen-1

y = alen-1

stk = []

while(ans>0):

    while(y>0):

        if dp[x][y-1] <= ans-1:

            break

        y -= 1

    while(x>0):

        if dp[x-1][y] <= ans-1:

            break

        x -= 1

    stk.append(strb[x])

    x -= 1

    y -= 1

    ans -= 1

stk.reverse()

print(''.join(map(str, stk)))

 

후기

적당히 2차원 DP테이블로 만들고, 해당 숫자가 가장 처음 만들어진 타이밍을 찾아가면서 추적했다.