[Python 3] BOJ - 9251 "LCS"

 # 문제 링크 : https://www.acmicpc.net/problem/9251

9251번: LCS

 

 # 풀이 :

 개인적으로 이 문제의 핵심은 LIS를 DP로 푼 것을 그저 2차원으로 확장시킨 것이라 생각한다. LIS, 가장 긴 증가하는 부분 수열처럼 LCS도 인덱스가 증가함에 따라 고를 수 있는 문자가 한정된다는 점, 그 길이가 최대가 되어야 한다는 점이 LIS와 비슷하게 접근이 가능하다. 하지만, LIS는 1차원 다이나믹으로 풀었다면, LCS는 비교해야 할 문자열이 2개이기 때문에 2차원 다이나믹으로 접근해야 한다.

<그림 1. ACAYKP와 CAP의 비교>

 String 2를 패턴이라고 가정하고 String 1을 비교하는 문자라고 생각해보자. 각각의 첫문자인 'C'와 'A'는 같지 않으므로 LCS의 길이는 0이다. String 2를 바깥쪽 for문, String 1을 안쪽 for문이라고 생각하면 이해가 더 빠를 것이다. 따라서 String 1의 두번째 문자인 'C'와 String 2의 첫번째 문자는 같다. 따라서 LCS의 길이는 1이다.

 그 다음 차례에서 중요한 순간이 일어나는데, String 1의 세번째 문자인 'A'와 String 2의 첫문자 'C'가 달라지는 순간이다. 이 경우는 어떻게 처리해야 할까? 두 문자열이 맞지 않으니 다시 LCS를 0으로 갱신하는 것은 옳지 않다. 가능한 경우는 2가지이다. 어차피 'A'와 'C'는 맞지 않음이 자명하므로 첫번째, 비교하는 문자열(String 1)은 그대로 둔채, 패턴(String 2)를 넣지 않는 경우와 두번째, 비교하는 문자열(String 1)을 넣지 않고 패턴(String 2)을 그대로 두는 경우이다.

<그림 2. 문자가 다른 경우>

 이 상황에서 'A'와 'C'를 비교할 때 LCS를 최대로 유지하려면 두 경우 중 LCS가 큰 경우를 선택하면 된다. 같은 논리로 'Y'와 'C'도 두 가지 경우 중 LCS가 더 큰 값을 취하면 정답을 구할 수 있다. 따라서, String 1의 인덱스를 i, String 2의 인덱스를 j라고 한다면 점화식은 다음과 같다.

 

 # 코드

import sys

# 입력부
a = sys.stdin.readline().rstrip()
b = sys.stdin.readline().rstrip()

# 인덱스 1부터 검사하기 위해 앞에 의미없는 문자열을 붙여줌
a = "0" + a
b = "0" + b

# table : 2차원 메모이제이션 테이블
table = [[0] * len(a) for _ in range(len(b))]
lcs = 0
for i in range(1, len(b)):
    temp = 0
    for j in range(1, len(a)):
        # 점화식
        if b[i] == a[j]:
            temp = table[i - 1][j - 1] + 1
            table[i][j] = temp
        else:
            table[i][j] = max(table[i][j - 1], table[i - 1][j])
    # 최대값 갱신
    if lcs < temp:
        lcs = temp
        
# 정답 출력
print(lcs)