백준 9251. LCS

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

9251번: LCS

 

문제

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

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

 

해답

공통 부분 문자열을 찾기 위해 표를 그려보면 위와 같다. 

같은 문자가 등장할 경우 +1, 그렇지 않을 경우 좌측 셀과 위측 셀의 최댓값을 가져오면 된다. 

 

s1 = input()
s2 = input()

l1 = len(s1)
l2 = len(s2)
dp = [[0] * (l2+1) for _ in range(l1+1)]
for i in range(1, l1+1):
	for j in range(1, l2+1):
		if s1[i-1] == s2[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(max(dp[l1]))