백준 1958 파이썬 python : LCS 3 @@황소처럼 우직하게@@

처음엔 아래 코드와 같이, a b c 의 lcs 는 (a b 의 lcs) 와 (c) 의 lcs 이겠지 생각했으나 틀렸다.

def lcs(a, b):
    dp = [[0 for i in range(len(a) + 1)] for j in range(len(b) + 1)]

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

def findit(a, dp):
    ans = ''
    now = dp[-1][-1]
    y = len(dp) - 1
    x = len(dp[0]) - 1
    while now != 0:
        if dp[y][x - 1] == now - 1 and now - 1 == dp[y - 1][x]:
            ans = a[x - 1] + ans
            now -= 1
            y -= 1
            x -= 1
        else:
            if dp[y - 1][x] > dp[y][x - 1]:
                y -= 1
            else:
                x -= 1
    return ans

lst = []
for i in range(3):
    lst.append(input())

lst.sort(key=lambda x: -len(x))

now_word = lst[0]
for i in range(1, 3):
    now_word = lcs(lst[i], now_word)
print(len(now_word))

 그냥 3차원 배열로 풀기로했다.

lst = [input() for i in range(3)]
dp = [[[0 for i in range(len(lst[0]) + 1)] for j in range(len(lst[1]) + 1)] for k in range(len(lst[2]) + 1)]

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

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

비교하는 것만 늘어났지. 간단하다

같으면 i - 1, j - 1, k - 1 인덱스 값 + 1 을 넣어준다. 다르면 6개 비교해줘서 큰 값 넣어준다.

길이뿐만아니라 부분문자열 찾으라는 문제도 나오면 재밌을거같다. ㅋㅋ

바로 다음 포스팅에서 해보도록하겠다.

(다음 포스팅은 아래 주소다)

https://hjp845.tistory.com/31

LCS 최장 공통 부분 수열 : 3개일 때 길이 뿐만 아니라, 부분문자열까지 찾아내기 @@황소처럼 우직하게@@