백준 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))