[백준 9251번] LCS (파이썬, 최장 공통 부분 수열, DP)

연속된 부분 수열은 아니고 각 문자열을 이루고 있는 문자들 순서만 맞춰서 최장 공통 부분 수열을 구하는 문제이다

 

a, b 두 문자열의 길이 +1 (각 첫번째 인덱스에 들어가는 값은 초기값인 0이다.)

인덱스 i,j를 비교해서 a와 b의 각 위치에 들어간 문자가 같다면 이전 최대 길이 +1 을 해주면 된다. 

 

1: acaykp , 2: capcak에서

 

1의 부분 문자인 a(인덱스 0)만 봤을 때 2에서 c인 경우 0, ca인 경우 1 이런식으로 추가되는 문자가 같다면 1 

증가시키는 식으로 해결한다.

 

 

import sys
input=sys.stdin.readline

a=input().strip() # 엔터키도 들어가지 않도록
b=input().strip()
# print(a,len(a))
dp=[[0]*(len(b)+1) for _ in range(len(a)+1)]

for i in range(1,len(a)+1):
    for j in range(1,len(b)+1):
        if a[i-1]==b[j-1]: # a,b는 0부터 시작, dp배열은 1부터 시작
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
print(dp[-1][-1])