해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 9251 LCS - dp

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

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

풀이

1. LCS(Longest Common Subsequence, 최장 공통 부분 수열)는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 부분을 말합니다.

2. ACAYKP를 비교 대상으로 잡고 CAPCAK 문자열 하나씩 추가하면서 공통 수열 길이 값을 DP 테이블에 표시해줍니다.

3. 문자열이 같으면 왼쪽 대각선 위의 값에 +1을 합니다.

4. 문자열이 같지 않으면, 왼쪽의 값과 위쪽의 값 중 큰 값을 넣습니다.

5. DP의 마지막 값인 DP[-1][-1]의 값이 최장 공통 부분 수열의 길이가 됩니다.

6. 위의 DP 테이블을 보면 노란색으로 칠한 부분이 최장 공통 부분 수열로 ACAK이고, 길이는 4가 됩니다.

전체 코드

m = ' ' + input()
n = ' ' + input()

dp = [[0] * (len(n)) for i in range(len(m))]

for i in range(1, len(m)):
    for j in range(1, len(n)):
        if m[i] == n[j]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[-1][-1])