Softeer - [21년 재직자 대회 본선] 비밀 메뉴2 (Python)

Lv3, ⭐⭐⭐

문제 풀이

• LCS (Longest Common Subsequence)와 유사하지만, 연속되어야하는 문제
  즉, Longest Common Continous Subsequence로 볼 수 있다.

• 기존의 LCS는 DP로 해결하는 만큼 이 문제 역시 DP로 해결해야 한다.

  • lst1, lst2의 길이 만큼의 2차원 리스트에서 값이 같다면 dp값을 증가시킨다.

from sys import stdin
n, m, k = map(int, stdin.readline().split())
lst1 = list(map(int, stdin.readline().split()))
lst2 = list(map(int, stdin.readline().split()))

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

for i in range(1, n + 1):
    for j in range(1, m + 1):
        if lst1[i - 1] == lst2[j - 1]:
            dp[i][j] = dp[i-1][j-1] + 1
            res = max(res, dp[i][j])

print(res)

기존의 LCS 풀이는 다음과 같다.

lst1 = list(map(int, stdin.readline().split()))
lst2 = list(map(int, stdin.readline().split()))
n = len(lst1)
m = len(lst2)

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

for i in range(1, n+1):
	for j in range(1, m+1):
    	if lst1[i-1] == lst2[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[-1][-1])