백준 1958 LCS3 파이썬
접근
처음 두 줄의 LCS 를 찾고, 그 결과와 마지막 줄의 LCS 를 찾는 순차적인 방법으로도 가능하다. 하지만 3차원 dp 로 처리하는 방법이 확장 가능성이 있기에 더 좋은 접근법이라 생각한다.
import sys
input = sys.stdin.readline
f = input().strip()
s = input().strip()
t = input().strip()
fl = len(f)
sl = len(s)
tl = len(t)
dp = [[[-1] * tl for i in range(sl)] for j in range(fl)]
def LCS(a, b, c):
if a < 0 or b < 0 or c < 0:
return 0
if dp[a][b][c] == -1:
dp[a][b][c] = 0
if f[a] == s[b] == t[c]:
dp[a][b][c] = LCS(a - 1, b - 1, c - 1) + 1
else:
dp[a][b][c] = max(max(LCS(a, b - 1, c), LCS(a - 1, b, c)), LCS(a, b, c - 1))
return dp[a][b][c]
print(LCS(fl - 1, sl - 1, tl - 1))
