[백준] LCS3

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

1958번: LCS 3

LCS를 응용하는 문제입니다. 3개의 문자열을 비교해야하므로 3차원 배열을 응용하여 풀이해주면 됩니다. 3개의 문자열의 현재 가르키고 있는 문자들이 같은 경우에는

dp[k][i][j] = dp[k - 1][i - 1][j - 1] + 1

와 같이 되고

 

문자가 다른 경우에는 3개의 문자열에서 각각 현재 가르키고 있는 문자열을 제외했을 때 얻을 수 있는 LCS 길이 중 최대를 선택해주면 됩니다.

dp[k][i][j] = max(dp[k - 1][i][j], dp[k][i - 1][j], dp[k][i][j - 1])

 

import heapq, sys

sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

str1 = input().rstrip()
str2 = input().rstrip()
str3 = input().rstrip()

n, m, l = len(str1), len(str2), len(str3)

str1 = "-" + str1
str2 = "-" + str2
str3 = "-" + str3



# dp[k][i][j] -> str3, str2, str1
dp = [
    [[0] * (n + 1)
    for _ in range(m + 1)]
    for __ in range(l + 1)
]


for k in range(1, l + 1):
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str3[k] == str2[i] == str1[j]:
                dp[k][i][j] = dp[k - 1][i - 1][j - 1] + 1
            else:
                dp[k][i][j] = max(dp[k - 1][i][j], dp[k][i - 1][j], dp[k][i][j - 1])

print(dp[l][m][n])