[백준/Python] LCS

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

9251번: LCS

이 문제는 전형적인 LCS 문제입니다. LCS 개념과 푸는 방법만 알면 쉽게 풀 수 있습니다. 먼저 두 문자열을 담은 2차원 리스트를 만듭니다. 그리고 문자 하나씩 비교해가면서 최장 수열의 개수를 세면 됩니다. 

 

최장 수열의 개수를 세는 방법은,

문자가 같은 경우 -> dp[i][j] = dp[i-1][j-1] + 1 (글자가 추가 되기 전 최대 길이 + 1)

문자가 다른 경우 -> dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (기존에 주어진 문자열로 만들 수 있던 최대 길이)

 

	0	C	A	P	C	A	K
0	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4

 

예시를 들어 이해를 해보자면,

dp[3][5] 일 때, 비교해야 할 문자열은 'ACA' 와 'CAPCA' 이다.

이 때 비교할 문자가 'A' == 'A' 로 같으므로 dp[3][5] = dp[2][4] + 1 = 3 이다. 글자가 추가 되기 전 최대길이에 +1를 하면 되는 것!

 

dp[4][5] 일 때, 비교해야 할 문자열은 'ACAY' 와 'CAPCA' 이다.

이 때 비교할 문자가 'Y' != 'A' 로 다르므로 dp[4][5] = max(dp[3][5], dp[4][4]) = max(3, 2) = 3 이다. 기존에 주어진 문자열로 만들 수 있던 최대 길이를 구하면 되는 것!

 

위를 바탕으로 코드는 금방 작성할 수 있다.

s1 = list(input())
s2 = list(input())
len1, len2 = len(s1), len(s2)
dp = [[0] * (len2+1) for _ in range(len1+1)]

for i in range(1, len1+1):
    for j in range(1, len2+1):
        if s1[i-1] == s2[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[-1][-1])