[BOJ 9251] LCS(Python)

문제

LCS

---

문제 해설

ACAYKP
CAPCAK
두 개의 문자열이 주어지고 가장 긴 공통 부분 수열을 찾는 문제입니다.

A
C
길이 : 0

A
CA
길이 : 1 (A)

A
CAP
길이 : 1 (A)
....
AC
C
길이 : 1 (C)

AC
CA
길이 : 1 (C)

AC
CAPC
길이 : 2 (AC)

이런식으로 완전 탐색을 하며 DP를 채우면 됩니다.
DP를 채우는 방식은 이런식으로 추가를 하다가 마지막 문자가 같을 시 길이가 늘어나는 것을 확인할 수 있습니다. 각 문자열이 해당 문자를 갖기 전의 최대 길이+1 입니다.

마지막 문자가 같지 않다면,
AC
CAPCA

A
CAPCA

AC
CAPC
이렇게 두 가지 경우 중 더 긴 길이를 가지고 있는 것을 택하면 됩니다.
점화식은
matrix[i][j] = matrix[i - 1][j - 1] + 1 (문자가 같을 시)
matrix[i][j] = max(matrix[i][j - 1], matrix[i - 1][j]) (문자가 다를 시)

DP를 모두 채우게 되면 각 문자열 상태에 대해 가장 긴 공통 부분 수열을 가지고 있는 상태가 됩니다.

---

풀이 코드

str1 = input()
str2 = input()

dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]
for i in range(len(str1)):
    for j in range(len(str2)):
        # 탐색 시 서로 같은 문자가 추가 된다면
        if str1[i] == str2[j]:
            # 같은 문자가 추가 되기 전 가장 긴 문자열 + 1
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            # 같은 문자가 아니면 str1, str2에서 문자 하나 뺀 것
            # str2, str1에서 문자 하나 뺀 것과 비교 후 큰 값 삽입
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
print(dp[len(str1)][len(str2)])

---