[백준 9251] LCS with Python

문제 링크

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

9251번: LCS

풀이

X = input()
Y = input()

LCS = [[0]*(len(Y)+1) for _ in range(len(X)+1)]

for i in range(1, len(X)+1):
    for j in range(1, len(Y)+1):
        if X[i-1] == Y[j-1]:
            LCS[i][j] = LCS[i-1][j-1] + 1
        else:
            LCS[i][j] = max(LCS[i][j-1], LCS[i-1][j])

print(LCS[len(X)][len(Y)])

두 문자열 X, Y가 있을 때, 두 문자열의 길이를 i, j라고 하고

두 문자열 X, Y를 아래와 같이 나타내겠다.

X = x₁x₂x₃...x_i-1x_i

Y = y₁y₂y₃...y_j-1y_j

그리고 LCS[i][j]를 X[:i]과 Y[:j]의 최장공통부문자열(LCS)이라고 하겠다.

 

 

먼저 LCS를 두 가지의 경우로 나누어 볼 수 있다.

1) x_i와 y_j가 같은 경우

x_i와 y_j가 같다면 해당 문자는 반드시 LCS의 마지막 문자가 된다.

왜냐하면, LCS는 "최장"공통부문자열이고,

두 문자열의 가장 마지막에 있는 공통 문자를 포함해야지만 문자열이 가장 길어지기 때문이다.

 

예를 들어

X = AABBC

Y = BABC

라고 하면

두 문자열의 LCS인 ABC, BBC에는 두 문자열의 동일한 마지막 문자인 C가 포함된다.

마지막 문자 C를 포함하지 않는 길이가 i-1, j-1인 X(AABB), Y(BAB)의 LCS(AB)의 길이인

LCS[i-1][j-1]는 LCS[i][j]에서 C가 없는 상태의 LCS이므로 1 차이가 난다.

즉, LCS[i][j] = LCS[i-1][j-1] + 1이라는 점화식을 세울 수 있다.

 

2) x_i와 y_j가 다른 경우

x_i와 y_j가 다르다면 LCS에 x_i와 y_j 둘 중 최소 하나는 반드시 포함되지 않는다.

이 경우의 LCS[i][j]는 둘 중 하나를 포함하지 않는 경우의 LCS의 길이 중 최댓값이다.

x_i가 포함되지 않은 경우 LCS의 길이는 LCS[i-1][j]이고,

y_j가 포함되지 않은 경우 LCS의 길이는 LCS[i][j-1]이다.

둘 다 포함되지 않는 경우는 어차피 LCS[i-1][j]와 LCS[i][j-1]이 같은 경우이므로 둘 중 어느 것을 택해도 상관 없다.

즉, LCS[i][j] = max(LCS[i][j-1], LCS[i-1][j])라는 점화식을 세울 수 있다.

 

위의 예시처럼 X = AABBC, Y = BABC일 때

LCS를 표로 나타내면 아래와 같다.

 

LCS[i][j]		j=0	j=1	j=2	j=3	j=4
			B	A	B	C
i=0		0	0	0	0	0
i=1	A	0	max(0, 0) = 0	0 + 1 = 1	max(1, 0) = 1	max(1, 0) = 1
i=2	A	0	max(0, 0) = 0	0 + 1 = 1	max(1, 1) = 1	max(1, 1) = 1
i=3	B	0	0 + 1 = 1	max(1, 1) = 1	1 + 1 = 2	max(2, 1) = 2
i=4	B	0	0 + 1 = 1	max(1, 1) = 1	1 + 1 = 2	max(2, 2) = 2
i=5	C	0	max(0, 1) = 1	max(1, 1) = 1	max(1, 2) = 2	2 + 1 = 3

 

i = 0인 경우와 j = 0인 경우는 인덱스를 맞추기 위한 부분이므로 모두 0이 된다.

그 외의 부분은 x_i와 y_j가 같으면 좌측 상단 대각선 방향의 칸의 숫자에 1을 더하고,

x_i와 y_j가 다르면 위 칸과 왼쪽 칸의 수 중 더 큰 값을 취한다.

 

최종적으로 LCS[i][j]에는 길이가 i인 X와 길이가 j인 Y의 LCS의 길이가 저장된다.