BOJ 9251 [LCS]

문제

문제 보기

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

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

풀이

아 dp 왤케 어렵냐.... 풀이봤다.

참조 링크

row를 기준으로 한다 했을 때 다음과 같다. dp[i][j]가 의미하는 것은 i와 j까지 비교했을 때 가장 긴 LCS 값이다.

'A'랑 비교한다 먼저. C, CA, CAP 하나씩 추가한다. 그러다가 'A'가 나오면 dp[i-1][j-1]+1을 한다. 최근에 추가한 값이 겹치는 경우이다. dp[i][j]가 i와 같아질 경우에는 더 이상 값이 커지지 못하므로 뒤에 값들을 다 i로 초기화 시키고 다음 row로 넘어간다.

만약 C나 CAP 처럼 'A'와 다른 경우에는 dp[i-1][j]와 dp[i][j-1]을 비교하여 큰 값을 택한다. 이때까지 진행한 가장 큰 값을 넣어주는 것이다. 이렇게 끝까지 진행하면 dp[-1][-1]에 우리가 원하는 정답이 나온다.

내 풀이는 표와 다르게 공집합을 빼서 index가 0부터 시작하는 풀이이다.

str1 = input()
str2 = input()

n = len(str1)
m = len(str2)

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

for i in range(m):
	for j in range(n):
		if str2[i] == str1[j]:
			if i>0 and j>0:
				dp[i][j] = dp[i-1][j-1] + 1
			else:
				dp[i][j] = 1

			if dp[i][j] == i+1:
				while j<n-1:
					j+=1
					dp[i][j] = i+1
				break

		else:
			dp[i][j] = max(dp[i-1][j],dp[i][j-1])

print(dp[m-1][n-1])