BOJ 9251 LCS

문제 : LCS

✅ 생각

Chan-Su Shin 님의 유튜브를 참고해서 작성했습니다.

📍 여기 2개의 문자열이 있다.

문자열 $X$ = A B C D E ...
문자열 $Y$ = X B C D X ...

각 문자열의 첫번째 문자를 $1$번으로,
문자열$X$의 $1$번부터 $i$번까지의 문자로 구성된 문자열을 $X_i$,
문자열$Y$의 $1$번부터 $i$번까지의 문자로 구성된 문자열을 $Y_i$ 라고 하자.

예를 들어, $X_3$ = A B C 이고, $Y_4$ = X B C D 이다.

📍 또 여기 $LCS$ 라는 함수가 있다.

$LCS$는 2개의 문자열을 인자로 받아서,
두 문자열의 LCS 길이를 반환한다.

예를 들어, $LCS(X_4, Y_4) = 3$ 이다. ( A B C D ), ( X B C D )

$LCS(X_6, Y_6)$ 을 구하기 위해서,
$X_5$, $Y_5$ 에 6번째 문자가 각각 새로 추가되었다고 생각 해보자.

두가지 경우가 있을 수 있다.

1. 추가된 6번째 문자가 서로 같을 때
2. 추가된 6번째 문자가 서로 같지 않을 때

📍 먼저, 같을 때 부터 확인해보자.

$X_5 =$ A B C D E
$Y_5 =$ X B C D X
일 때, $LCS(X_5, Y_5)$ = 3 이다.

그리고 6번째 문자가 새로 추가되었다.

$X_6 =$ A B C D E + P
$Y_6 =$ X B C D X + P

새로 추가된 두 문자가 같기 때문에,
LCS의 길이는 1 증가한다.

이렇게 쓸 수도 있겠다.

$LCS(X_6, Y_6)$ = $LCS(X_5, Y_5)$ + 1

그리고 이것은 두 문자열의 길이와 관계없이 성립할 것이다.

$X$의 $i$번째 문자와, $Y$의 $j$번째 문자가 같을 때,

$LCS(X_i, Y_j) = LCS(X_{i-1}, Y_{j-1})$ + 1

📍 그 다음, 다를 때를 생각해보자

이때는 3가지 경우가 생긴다.

1. $X_5$에 추가된 문자가 LCS의 길이를 증가시킨다.
   $X_6 =$ A B C D E + X
   $Y_6 =$ X B C D X + M

2. $Y_5$에 추가된 문자가 LCS의 길이를 증가시킨다.
   $X_6 =$ A B C D E + Q
   $Y_6 =$ X B C D X + E

3. 추가된 두 문자 모두 LCS 길이에 영향을 주지 못한다.
   $X_6 =$ A B C D E + Q
   $Y_6 =$ X B C D X + M

3가지 경우에서,
LCS의 길이가 증가하는 경우를 찾기위해 해 주어야 할 질문은
어떤 문자열에 새로운 문자를 추가했을 때 LCS 길이가 증가하나요? 이다.
( 3번 처럼 길이가 증가하지 않을 수도 있다. )

• $X_5$에만 6번째 문자를 추가할 때
• $Y_5$에만 6번째 문자를 추가할 때

이 두 가지 경우의 LCS길이 중 큰 값이
$LCS(X_6, Y_6)$ 이다.

얘도 이렇게 써줄 수 있고,

$LCS(X_6, Y_6)$ = $LCS(X_6, Y_5)$ 와 $LCS(X_5, Y_6))$ 중에 큰 값

마찬가지로, 이렇게도 써 줄 수 있다.

$X$의 $i$번째 문자와, $Y$의 $j$번째 문자가 같지 않을 때,

$LCS(X_i, Y_j) = \max(\ LCS(X_i, Y_{j-1}),\ LCS(X_{i-1}, Y_j)\ )$

📍 사실은

LCS가 2차원 배열이라면 어떨까?

두 문자열의 문자를 차례로 비교하면서,
위에서 설명한 것처럼
같을 경우와 다를 경우를 나누어 갱신해준다.

[ 전체 코드 ]

import sys

sequence1 = sys.stdin.readline().rstrip()
sequence2 = sys.stdin.readline().rstrip()

n = len(sequence1)
m = len(sequence2)

LCS = [[0] * (m+1) for _ in range(n+1)]
for i in range(1, n+1):
    s1 = sequence1[i-1]
    for j in range(1, m+1):
        s2 = sequence2[j-1]
        if s1 == s2:
            LCS[i][j] = LCS[i-1][j-1] + 1
        else:
            LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])

sys.stdout.write(f'{LCS[n][m]}')