나의 풀이
# 입력
import sys
read = sys.stdin.readline
A, B = read().strip(), read().strip()
n, m = len(A), len(B)
LCS = [[''] * (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] + A[i - 1]
else:
if len(LCS[i - 1][j]) > len(LCS[i][j - 1]):
LCS[i][j] = LCS[i - 1][j]
else:
LCS[i][j] = LCS[i][j - 1]
print(LCS[n][m])
CODE REVIEW
- 문제를 풀다가 도저히 해결 방법을 모르겠어서 구글링을 통해 LCS 알고리즘에 대해 알게 되었다. 아래 블로그에 그림으로 잘 설명되어있었는데,
n*m matrix에 경로에 따라 +1 해가면서 빈칸을 채우는 기발한 방법으로 문제를 풀어낼 수 있었다. - 숫자를 채워넣는 LCS 알고리즘을 응용해서, matrix속에 조건을 만족하면 문자열 string을 추가하는 방식으로 문제를 해결했다.
- dp 문제는 정말 생각지도 못한 기발한 풀이법들이 존재해서 항상 배우게 하는 것 같다.