[백준 9252] LCS 2 - 최장 공통 부분 수열

https://www.acmicpc.net/problem/9252

9252번: LCS 2

문제

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

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

입력

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

출력

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

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

 

 

---

최장 공통 부분 수열(Longest Common Subsequence) 문제이다.

이 문제에서는 두 문자열의 LCS의 길이뿐만 아니라, LCS 또한 출력해야 한다는 점이 포인트이다.

 

 

 LCS의 길이 구하기

 

최장 공통 부분 수열 점화식

 

점화식에 따라 dp배열을 만들면 다음과 같다.

전체 시간 복잡도는 O(len(a)*len(b))이다.

   -  C  A  P  C  A  K
-  [0, 0, 0, 0, 0, 0, 0]
A [0, 0, 1, 1, 1, 1, 1]
C [0, 1, 1, 1, 2, 2, 2]
A [0, 1, 2, 2, 2, 3, 3]
Y [0, 1, 2, 2, 2, 3, 3]
K [0, 1, 2, 2, 2, 3, 4]
P [0, 1, 2, 3, 3, 3, 4]

 

 LCS 구하기

• dp배열의 (len(a), len(b))의 위치부터 시작한다.
• 왼쪽과 위쪽 값 중 하나 이상의 위치만 현재값과 다르다면 같은 값을 가지는 쪽으로 계속해서 이동한다.
• 현위치의현 위치의 왼쪽과 위쪽의 값이 모두가 현재값과 다르다면 현 위치의 알파벳을 배열에 담고 좌측 위로 이동한다.
• 현재값이 0이 될 때까지 반복한다.
• 담아왔던 배열을 뒤집은 것이 LCS이다.

 

즉, 길이가 변하는 시점이 LCS에 포함되는 부분인 것이다.

LCS는 여러 값이 나올 수 있다.

 

 

 

 

<< 전체 코드 >>

import sys
input = sys.stdin.readline

a = input().rstrip()
b = input().rstrip()
dp = [[0 for _ in range(len(b)+1)] for _ in range(len(a)+1)]

i, j = 1, 1
while i <= len(a) and j <= len(b):
    if a[i-1] == b[j-1]:
        dp[i][j] = dp[i-1][j-1] + 1
    else:
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    i += 1
    if i > len(a):
        j += 1
        i = 1

answer = []
i, j = len(a), len(b)
while dp[i][j]:
    if dp[i-1][j] == dp[i][j]:
        i -= 1
    elif dp[i][j-1] == dp[i][j]:
        j -= 1
    else:
        answer.append(a[i-1])
        i -= 1
        j -= 1

print(dp[len(a)][len(b)])
print(''.join(reversed(answer)))