9251번: LCS 가장 긴 공통 부분수열 (DP) - Fastcampus

www.acmicpc.net/problem/9251

9251번: LCS

# dp[i][j] = 공통 부분 문자열의 최대길이
#            (i번째까지의 문자열, j번째까지의 문자열)
#
# dp[i][j] = (같은 값) 대각선 + 1  => dp[i-1][j-1] + 1
#            (다른 값) 위 + 1 or 왼쪽 + 1 => max(dp[i-1][j] or dp[i][j-1])
#
#    C  A  P  C  A  K
# A  0  1  1  1  1  1
# C  1  1  1  2  2  2
# A  1  2  2  2  3  3
# Y  1  2  2  2  3  3
# K  1  2  2  2  3  4
# P  1  2  3  3  3  4

def run(s1, s2):
    N, M = len(s1), len(s2)
    dp = [[0] * (M+1) for _ in range(N+1)]
    s1, s2 = " " + s1, " " + s2

    for i in range(1, N+1):
        for j in range(1, M+1):
            if s1[i] == s2[j]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[N][M]


s1 = input()
s2 = input()
print(run(s1, s2))