[Python/파이썬] 백준 9251번 LCS

9251번: LCS

 

문제

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

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

코드

str1 = input()
str2 = input()
dp = [[0]*(len(str2)+1) for _ in range(len(str1)+1)]
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)])

dp 배열에 str1과 str2의 문자들을 하나하나 비교하여 부분 수열 중 가장 긴 길이를 저장한다.

점화식은 다음과 같다.

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])

지금 보고 있는 str1과 str2의 문자가 같아서 최장 공통 부분 수열에 포함된다면 dp[i-1][j-1]에서 지금 문자의 길이 1을 더하여 dp[i][j]에 저장해준다. 그렇지 않다면 이 문자는 최장 공통 부분 수열에 포함될 수 없으므로 이 문자 하나 이전의 값 중 큰 값을 그냥 가져온다.

 

좀 이해하기 쉽게 그림으로 나타내보자면 다음과 같다. str1이 행, str2가 열이라고 하자.

편의상 문자열의 인덱스는 1부터 시작한다고 할 때, dp[i][j]에는 str1의 i번째 문자, str2의 j번째 문자까지의 부분 수열 중 가장 긴 것의 길이가 저장된다. 예를 들어, str1이 ACAYKP, str2가 CAPCAK라 할 때, dp[3][4]에는 ACA, CAPK의 최장 공통 부분 수열 CA의 길이인 2가 저장되는 것이다.