[BOJ][🟡4][백준#09252] LCS 2

문제 출처

BAEKJOON Online Judge #9252

문제

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

입력

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

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다. LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

예제

입력

ACAYKP
CAPCAK

출력

4
ACAK

My Sol

A = input()
B = input()
al, bl = len(A), len(B)
LCS = [[[0, ''] for _ in range(bl+1)] for _ in range(al+1)]

for i in range(1, al+1):
    for j in range(1, bl+1):
        LCS[i][j] = sorted([LCS[i][j-1], LCS[i-1][j]], key=lambda x:-x[0])[0]
        if A[i-1] == B[j-1]:
            n, txt = LCS[i-1][j-1]
            if n >= LCS[i][j][0]:
                LCS[i][j] = [n+1, txt+A[i-1]]

ret = LCS[al][bl]
if ret[0]:
    for a in ret:
        print(a)
else:
    print(0)

LCS를 해결하는 DP를 사용했다.

1. 두 텍스트를 각각 A, B로 두고 이 길이를 al, bl로 계산하였다.
2. 이 al과 bl을 각각 행과 열로 두는 2차원 배열 LCS를 만들고, 각 칸을 최초 길이인 0과 빈 값을 가진 배열로 초기화한다.
3. 각 행과 열을 돌며 A와 B의 한 알파벳이 같고, 직전까지 가능한 최대공통부분의 길이가 현재 칸의 공통 부분의 길이보다 같거나 크다면 이번 LCS칸을 (i-1, j-1)에 알파벳을 하나 붙인 것으로 간주한다.
4. LCS[i][j-1]와 LCS[i-1][j] 중 길이가 더 긴 것을 각 칸의 완전탐색에서 초기화한다.
5. LCS[al][bl]이 결과이고, 이 값이 0이라면 0만, 아니라면 길이와 텍스트를 출력한다.

결과

맞았습니다!!