[백준] 9251번 - LCS (파이썬)

문제) 백준 - 동적 계획법 (Dynamic Programming) - LCS

-> www.acmicpc.net/problem/9251

9251번: LCS

 

dp를 해당 문자 이전까지 만들 수 있는 LCS라 하자.

dp를 업데이트 해가며 만약 문자열이 같을 경우(string1[i] == strring2[j]), 이전 LCS의 길이(dp[i - 1][j  - 1])에 1을 더해준다.

문자가 같지 않을 경우, 이전에 만든 LCS중 최대값을 그대로 가져온다.(max(dp[ i - 1 ][ j ], dp[ i ][ j - 1 ]))

 

 

 

소스 코드)

import sys
input = sys.stdin.readline
string1 = list(input().rstrip())
string2 = list(input().rstrip())
string1len = len(string1)
string2len = len(string2)

dp = [[0] * (string2len + 1) for i in range(string1len + 1)]
for i in range(string1len):
    for j in range(string2len):
        if string1[i] == string2[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[string1len][string2len])