Koala - 12기/코딩테스트 준비 스터디
[백준/phthon3] 9251번: LCS
יוֹסֵף
2023. 9. 18. 12:22
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
문제
코드
A=input()
B=input()
dp=[[0]*1001 for _ in range(1001)]
ans=0
for i in range(1, len(A)+1):
for j in range(1, len(B)+1):
if A[i-1]==B[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ans=max(ans, dp[i][j])
print(ans)