백준 1958번 : LCS 3 in Python

1958번: LCS 3

 

www.acmicpc.net

이 문제는 문자열 3개의 LCS를 구하는 문제이다.

문자열 2개의 LCS를 구하는 방법을 이용하면 문자열 3개의 LCS 역시 쉽게 구할 수 있다. 문자열 2개의 LCS는 두 문자열의 각 문자에 대해 순회하면서 만약 한 문자열의 i번째 문자, 다른 문자열의 j번째 문자가 같은 경우에는 dp[i][j] = dp[i-1][j-1] + 1로 계산하고, 다른 경우에는 dp[i][j]를 dp[i-1][j]와 dp[i][j-1] 중 더 큰 값으로 한다.

문자열이 3개인 경우에도 행렬의 차원을 1 증가시켜 위와 같은 방식으로 하면 된다. 즉, 3개의 문자열의 각 문자에 대해 순회하면서 만약 첫 번쨰 문자열의 i번째 문자, 두 번째 문자열의 j번째 문자, 세 번째 문자열의 k번째 문자가 같은 경우에는 dp[i][j][k] = dp[i-1][j-1][k-1] + 1, 다른 경우에는 dp[i][j][k]를 dp[i-1][j][k], dp[i][j-1][k], 그리고 dp[i][j][k-1] 중 가장 큰 값으로 하면 된다.

이를 코드로 구현하면 다음과 같다.

str1 = input()
str2 = input()
str3 = input()
a = len(str1)
b = len(str2)
c = len(str3)
dp = [[[0]*(c+1) for _ in range(b+1)] for _ in range(a+1)]
for i in range(1, a+1):
    for j in range(1, b+1):
        for k in range(1, c+1):
            if str1[i-1] == str2[j-1] and str2[j-1] == str3[k-1]:
                dp[i][j][k] = dp[i-1][j-1][k-1] + 1
            else:
                dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])
print(dp[a][b][c])