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

가장 긴 공통 부분 수열을 찾는 문제이다.
가장 긴 증가 부분 수열은 아는데 공통이 들어가서 처음에는 가장 작은 문자열을 기준으로 모든 부분 문자열에 대해서 공통된 부분을 찾아야 하는가 생각했다가 다른 방법을 찾아보았다.

emplam27 - [알고리즘] 그림으로 알아보는 LCS 알고리즘
위 블로그를 참고해서 이러한 유형의 문제를 어떻게 접근해야하는 지 이해했다. 그리고 여기에 더 해서 3차원으로 리스트를 만들어서 해결했다.
처음에는 문제에서 계속 문자열이라고 하길래 가장 긴 공통 문자열을 찾는가 했다가 문제를 다시 읽어보니

문자열 2개의 LCS(Longest Common Subsequence)

즉, 수열을 찾는 문제여서 해당 방식으로 해결했다.

Python

a = input().strip()
b = input().strip()
c = input().strip()

dp = [[[0] * (len(a)+1) for _ in range(len(b)+1)] for _ in range(len(c)+1)]

for i in range(len(c)+1):
  for j in range(len(b)+1):
    for k in range(len(a)+1):
      if i == 0 or j == 0 or k == 0:
        dp[i][j][k] = 0
      elif c[i-1] == b[j-1] == a[k-1]:
        dp[i][j][k] = dp[i-1][j-1][k-1] + 1
      else:
        dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])
ans = 0    
for d in dp:
  for p in d:
    ans = max(ans, max(p))
print(ans)