[백준 Python] 1958번 LCS 3

백준 파이썬 1958번 LCS 3

Gold 4

 

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

 

3개의 문자열을 비교하는 LCS 문제다 !

처음에 a와 b를 비교하고, 그 비교값을 c와 비교하는 LCS 계산을 두 번 하는 방법으로 접근해서 푸는데 생각보다 오래 걸렸다.

위와 같은 방식으로 접근을 하면 첫 계산에서 무조건 긴 문자열만 고르기 때문에 정답이 나올 수 없다.

abcd
abdc
c

기댓값 => 1, 결괏값 => 0

그렇기 때문에 3차원 리스트를 생성해서 값을 비교해주어야 한다.

a = input()
b = input()
c = input()
dp = [[[0]*(len(c)+1) for _ in range(len(b)+1)] for _ in range(len(a)+1)]
for i in range(1, len(a)+1):
    for j in range(1, len(b)+1):
        for k in range(1, len(c)+1):
            if a[i-1] == b[j-1] == c[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[-1][-1][-1])

 

+ 처음에 dp를 dp1 = [[[0]*(len(c)+1)]*(len(b)+1) for _ in range(len(a)+1)]로 잘못 생성해서 계속 오답이 떴었다.

dp2 = [[[0]*(len(c)+1) for _ in range(len(b)+1)] for _ in range(len(a)+1)] 와 같아 보일 수 있지만 dp1은 [[0]*(len(c)+1)]가 얕은 복사를 하게 되어 dp1[0][1][1] = 1를 해주게 되면 dp1: [[0, 1, 0, 0], [0, 1, 0, 0], [0, 1, 0, 0], [0, 1, 0, 0]] 이렇게 값들이 의도한 바와 다르게 대입될 수 있다.

주의하기 !