[99클럽/파이썬 챌린저/34일차] LCS 3

백준 1958번 LCS 3 G4

 

문제
문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다. 이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.

입력
첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다.

출력
첫 줄에 첫 번째 문자열과 두 번째 문자열과 세 번째 문자열의 LCS의 길이를 출력한다.

 

 

문자열, 다이나믹 프로그래밍

 

3차원 DP를 통해 풀이하였다.

2개의 문자열에서 구한 lcs와 비교하는 방식은 최적의 해를 보장하지 못한다.

 

이전에 2개의 문자열에서 사용한 점화식을 조금 변경하여 풀이하였다.

 

dp [i][j][k] = dp [i-1][j-1][k-1] + 1 if a [i] == b [j] == c [k] else max(dp [i][j][k-1], dp [i][j-1][k], dp [i-1][j][k])

 

 

import sys

a = '0' + sys.stdin.readline().rstrip()
b = '0' + sys.stdin.readline().rstrip()
c = '0' + sys.stdin.readline().rstrip()

dp = [[[0] * len(c) for _ in range(len(b))] for _ in range(len(a))]

for i in range(1, len(a)):
    for j in range(1, len(b)):
        for k in range(1, len(c)):
            if a[i] == b[j] and a[i] == c[k]:
                dp[i][j][k] = dp[i-1][j-1][k-1] + 1
            else:
                dp[i][j][k] = max(dp[i][j][k-1], dp[i][j-1][k], dp[i-1][j][k])

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

 

---