백준 9251 LCS (파이썬)
접근방식
- LCS는 Longest Common Subsequence의 준말로 최장 공통 부분 수열을 의미한다.
- 이 문제는 최장 공통 부분 수열을 구하는 것이 아닌 카운트하는 문제였다.
- LCS의 기본 점화식은 다음과 같다. 이 점화식을 기본으로 문제를 해결하면 된다.
파이썬 코드
import sys
x = list(sys.stdin.readline().strip('\n'))
y = list(sys.stdin.readline().strip('\n'))
x.insert(0,'0')
y.insert(0,'0')
m = len(x)
n = len(y)
c = [[0]* (n) for _ in range(m)]
for i in range(1,m):
for j in range(1,n):
if x[i] == y[j]:
c[i][j] = 1 + c[i-1][j-1]
else:
c[i][j] = max(c[i-1][j], c[i][j-1])
print(c[m-1][n-1])
