[알고리즘] 백준 - LCS

백준 - LCS

내 풀이

import sys, copy
from collections import deque

str1 = list(input())
str2 = list(input())

dp = [[0]* (len(str2)+1)  for _ in range(len(str1)+1)]

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(max(max(dp)))

예전에 풀었던 문제인데 풀지 못했다.

점화식 설명
dp[i][j]는 str1의 i번째까지와 str2의 j번째까지 비교했을 때 가장 긴 수열이다.

Case1: 만약 str1의 i번째 문자와 str2의 j번째 문자가 다르다면 길이는 dp[i-1][j]와 dp[i][j-1]중 최대 값이다 (기존에 주어진 문자열로 만들 수 있던 최대 길이)

Case2: 만약 str1의 i번째 문자와 str2의 j번째 문자가 같다면 dp[i-1][j-1] + 1이다. (두 글자가 추가되기 전 가장 큰 길이 + 1)

자세한 설명 블로그