[백준] 9251번 LCS 파이썬 풀이

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

9251번: LCS

---

1. 풀이

• 가장 뒤의 문자부터 검사하자

맨 뒤 문자부터 서로 비교하면서 (1) 같으면 두 문자열에서 동시에 마지막 문자를 제거하고 (2) 다르면 문자열1의 마지막 문자만 제거하거나 문자열2의 마지막 문자만 제거하는 식으로 2가지 갈래로 나누어 가자.

더 이상 문자열을 비교할 수 없을 때는, 그 동안 동시에 제거된 문자 (C, E)가 바로 두 문자열의 LCS이다.

 

 

• dp를 사용하자

dp 테이블

dp 말고 재귀를 사용할 수 있지만, 동일한 연산을 반복하기 때문에 컴퓨터가 계산할 수 없는 수준에 다다르게 된다 (Overlapping Subproblems). 따라서 재귀를 사용한 탑다운 방식 대신에 dp를 통해 바텀업 방식을 사용하자!

dp 테이블을 채우는 방법은 재귀와 동일하다. (1) 행과 열의 문자가 동일하면 (i - 1, j - 1)의 값에 1을 더하고 (2) 다르면 이전 행 (i - 1, j) 이나 이전 열 (i, j - 1) 중 더 큰 값을 채운다.

이때 (i - 1, j - 1)은 문자열1의 인덱스 0부터 (i - 1)까지의 서브 문자열1과 문자열2의 인덱스 0부터 (j - 1)까지의 서브 문자열2의 LSC 길이를 나타낸다. (i - 1, j)와 (i, j - 1) 역시 각 문자열1과 문자열2의 서브 문자열 간 LSC 길이이다.

 

 

 

 

2. 정답 코드

def getLSC(x, y):
    x = ' ' + x
    y = ' ' + y
    x_n = len(x)
    y_n = len(y)

    dp = [[0] * x_n for _ in range(y_n)]

    for i in range(1, y_n):
        for j in range(1, x_n):
            if x[j] == y[i]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[y_n - 1][x_n - 1]


str1 = input()
str2 = input()

print(getLSC(str1, str2))