Longest Common Subsequence

백준 9251번: LCS

아이디어

DP 테이블에 해당 문자열로 만들 수 있는 Longest Common Subsequence의 길이를 저장한다.

2차원 배열의 인덱스와 두 문자열의 인덱스를 매칭시킨다. 예를 들어 주어진 문자열이 ACAYKP, CAPCAK라 하자. 이 때 dp[2][5]에는 AC와 CAPCA의 Longest Common Subsequence 길이를 저장한다. 그 길이는 2가 될 것이다. dp[2][6]에는 ACA와 CAPCA의 LCS 길이를 저장한다. 그 길이는 3이 될 것이다.

코드

import sys
input = sys.stdin.readline

str1 = input().rstrip()
str2 = input().rstrip()

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

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

여담

LCS와 관련된 문제가 굉장히 많다. 다 풀어보면 큰 도움이 될 것이다.
백준 9252번: LCS2
백준 1958번: LCS3
백준 5582번: 공통 부분 문자열