[Python]백준 9251번/LCS/dp

🧉  문제 설명 

https://www.acmicpc.net/problem/9251

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

🧉  해결 방법

문자열 두개를 비교하면서

문자가 같으면 그 전번째의 가장 긴 길이인 왼쪽에 위쪽 대각선방향의 숫자에서 +1 을 한다.

문자가 다르면 왼쪽과 위쪽의 값중 가장 큰 값을 넣는다.

 

🧉  코드

import sys
input=sys.stdin.readline

stringA=list(input().rstrip())
stringB=list(input().rstrip())

dp=[[0]*(len(stringB)+1) for _ in range(len(stringA)+1)]
for i in range(len(stringA)):
    for j in range(len(stringB)):
        if(stringA[i]==stringB[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[len(stringA)][len(stringB)])