알고리즘/백준
[백준] 9251번 LCS (파이썬)
알감자
2022. 1. 2. 01:16
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
코드
m = list(input())
n = list(input())
m_len = len(m)
n_len = len(n)
dp = [[0] * (n_len + 1) for i in range(m_len + 1)]
for i in range(m_len):
for j in range(n_len):
if m[i] == n[j]:
dp[i + 1][j + 1] = dp[i][j] + 1
else:
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
print(dp[m_len][n_len])