나의 풀이
# 입력
import sys
read = sys.stdin.readline
A, B = read().strip(), read().strip()
n, m = len(A), len(B)
LCS = [[0] * (m + 1) for _ in range(n + 1)]
# 처리 - LCS 알고리즘 이용
for i in range(1, n + 1):
for j in range(1, m + 1):
if A[i - 1] == B[j - 1]:
LCS[i][j] = LCS[i - 1][j - 1] + 1
else:
LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])
print(LCS[n][m])
CODE REVIEW
- 백준 9251번 - LCS를 풀면서 3개 이상의 문자열의 LCS 구하는 문제도 만들어볼 수 있겠다 생각했는데, 역시나 이미 그런 문제가 존재했다.
- 3중 array를 사용하면 되었는데 2차원을 3차원으로 확대하는 과정이 생각보다 단순해서 금세 해결 가능했다.
- 문제에서 요구하진 않았지만, 역추적 하면 LCS에 해당하는 string 문자열을 구할 수도 있다.