[DP(Dynamic Programming)] 백준-9251 LCS 골드5 (Python)

백준-9251 : LCS

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

9251번: LCS

 

 

풀의

• 두 문자를 글자마다 비교할 2차원 배열을 생성한다.
• 문자 하나를 기준을 잡는다.
• 두번째 문자열과 비교하면서 값을 업데이트 한다.
  • 문자열이 동일한 경우 : 이전 dp의 1을 더한값을 저장한다.
  • 문자열이 다른 경우 : 이전 좌표의 값들중 큰값을 저장한다.

 

코드 (Python)

import sys

def input():
    return sys.stdin.readline().rstrip()

str1 = input()
str2 = input()

dp = [[0] * (1001) for _ in range(1001)]

for i in range(1,len(str1)+1):
    for j in range(1,len(str2)+1):
        if (str1[i-1] == str2[j-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[len(str1)][len(str2)])