[백준] LCS

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

9251번: LCS

 

두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

이차원 배열로 수열을 비교하여,

 

1) 같은 문자일 때, dp[i][j] = dp[i-1][j-1] (두 수열에서 같은 문자가 추가되기 전의 최댓값) + 1

ACAYK 와 CAPCAK 의 LCS 의 길이는 ACAY 와 CAPCA 의 LCS 의 길이의 + 1 이다. 

 

2) 다른 문자일 때, dp[i][j] = max(dp[i][j-1], dp[i-1][j]) (현재까지의 부분 수열이 되는 수열 중 가장 긴 것의 길이)

ACAY 와 CAPCA 의 LCS 길이는 ACA 와 CAPCA 의 LCS 길이(3)와 ACAY 와 CAPC 의 LCS 길이(2) 중 최댓값이다. 

 

import sys

S1 = sys.stdin.readline().strip()
S2 = sys.stdin.readline().strip()
dp = [[0] * (len(S2) + 1) for i in range(len(S1) + 1)]

for i in range(1, len(S1)+1):
    for j in range(1, len(S2)+1):
        if S1[i-1] == S2[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

print(dp[-1][-1])