[Python] 백준 1958번: LCS 3

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

1958번: LCS 3

1. 그렇다 3차원배열을 쓰면 쉽게 해결가능한 문제이지만 2차원배열로 풀어보았다.

2. 밑에가 3차원이고 위에가 2차원으로 풀었다.

3. 위의 방법은 권장하지않는다..

s = []
for _ in range(3):
    s.append(input())
dp = [[0 for _ in range(101)] for _ in range(101)]
ans = 0


def maxLCS(x, y):
    tmp = 0
    for i in range(x):
        for j in range(y):
            tmp = max(tmp, dp[i][j])
    return tmp


for i in range(len(s[0])):
    for j in range(len(s[1])-1, -1, -1):
        if s[0][i] == s[1][j]:
            for k in range(len(s[2])-1, -1, -1):
                dp[j][k] = max(dp[j][k], dp[j][k-1], dp[j-1][k])
                if s[1][j] == s[2][k]:
                    dp[j][k] = max(dp[j][k], maxLCS(j, k)+1)
                    ans = max(ans, dp[j][k])

print(ans)

 

a, b, c = ['\0' + input() for _ in range(3)]
dp = [[[0 for _ in range(len(c)+1)] for _ in range(len(b)+1)]
      for _ in range(len(a)+1)]
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] == c[k]:
                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[-2][-2][-2])