알고리즘 스터디 - 백준 9252번 : LCS2 (feat. Python)

문제 해석

LCS는 해커랭크에서 제공해주는 강의를 듣고 DP를 이용해 어떻게 문제를 풀었는지 알 수 있었다. 기존 LCS를 적용할 때는 0에서 1로 1에서 2로 증가하는 방식을 이용을 했는데 이번 문제에서는 LCS의 문자까지 출력하도록 하는 문제다.

예를 들어, ACAYKP와 CAPCAK가 있을 때 기존 문제는 공통 개수를 출력하는 거로 4지만 이번 스페셜 저지 문제는 4와 함께 공통부분이 있는 문자열을 출력하는 것으로 4와 ACAK이다.

알고리즘 코드

기존 LCS 리스트를 길이를 저장하는 숫자와 문자열이 있는 리스트를 생성하고 숫자와 문자열을 더하거나 상속받는 방식을 진행을 하였다.

A = list(input())
B = list(input())

lcs = [[[0, ""] for _ in range(len(B)+1)] for _ in range(len(A)+1)]

for i in range(1, len(A)+1):
    for j in range(1, len(B)+1):
        if A[i-1] == B[j-1]:
            lcs[i][j][0] = lcs[i-1][j-1][0] + 1
            lcs[i][j][1] = lcs[i-1][j-1][1] + A[i-1]
        else:
            if lcs[i][j-1][0] > lcs[i-1][j][0]:
                lcs[i][j][0] = lcs[i][j-1][0]
                lcs[i][j][1] = lcs[i][j-1][1]
            else:
                lcs[i][j][0] = lcs[i-1][j][0]
                lcs[i][j][1] = lcs[i-1][j][1]

print(lcs[len(A)][len(B)][0])
print(lcs[len(A)][len(B)][1])