LCS3

출처 : 백준 #1958

시간 제한	메모리 제한
2초	128MB

---

문제

첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다.

---

입력

첫 줄에 첫 번째 문자열과 두 번째 문자열과 세 번째 문자열의 LCS의 길이를 출력한다.

---

입출력 예시

예제 입력 1

abcdefghijklmn
bdefg
efg

예제 출력 1

3

---

풀이

생각 및 풀이 설명

• 처음엔 가장 짧은 문자열과 중간 길이의 문자열의 LCS를 먼저 구한 뒤 가장 긴 문자열과의 LCS를 구해서 답을 찾고자 하였다.
• 허나 이렇게 했을 때 반례가 존재한다.
  • ABCBDAB, BDCABA
  • 처음 두 문자열을 비교한다고 가정한다.
  • LCS로 하나의 답만 존재하는 것이 아니다.
  • BDAB, BCBA 가 존재한다.
  • 따라서 가능한 모든 LCS를 구해서 비교를 해야하지만,
    그것보다는 세 문자열을 한 번에 3차원의 배열로 구하는 것이 훨씬 간편했다.

python code(처음 풀이 - 오답)

# 백준 1958번 LCS3 (문자열)
import sys
from heapq import heappop, heappush
input = sys.stdin.readline

x = "%"+input().rstrip()
y = "%"+input().rstrip()
z = "%"+input().rstrip()

temp = []
heappush(temp, (len(x), x))
heappush(temp, (len(y), y))
heappush(temp, (len(z), z))

len1, str1 = heappop(temp)
len2, str2 = heappop(temp)
len3, str3 = heappop(temp)
C = [([0] * len1) for _ in range(len2)]
result = "%"
for i in range(len2):
    for j in range(len1):
        if i == 0 or j == 0:
            C[i][j] = 0
        elif str1[j] == str2[i]:
            C[i][j] = C[i-1][j-1] + 1
            result += str1[j]
        else:
            C[i][j] = max(C[i][j-1], C[i-1][j])
print(result)
S = [0] * len(result)
for i in range(1, len3):
    for j in range(len(result)):
        if j == 0:
            S[j] = 0
        elif str3[i] == result[j]:
            S[j] += 1
        else:
            S[j] = max(S[j], S[j-1])

print(S[-1])

python code(정답 코드)

# 백준 1958번 LCS3 (문자열)
import sys
from heapq import heappop, heappush
input = sys.stdin.readline

x = "%"+input().rstrip()
y = "%"+input().rstrip()
z = "%"+input().rstrip()

temp = []
heappush(temp, (len(x), x))
heappush(temp, (len(y), y))
heappush(temp, (len(z), z))

len1, str1 = heappop(temp)
len2, str2 = heappop(temp)
len3, str3 = heappop(temp)
C = [[([0] * len1) for _ in range(len2)] for _ in range(len3)]

for k in range(len3):
    for i in range(len2):
        for j in range(len1):
            if i == 0 or j == 0 or k == 0:
                C[k][i][j] = 0
            elif str1[j] == str2[i] and str2[i] == str3[k]:
                C[k][i][j] = C[k-1][i-1][j-1] + 1
            else:
                C[k][i][j] = max(C[k-1][i][j], C[k][i-1][j], C[k][i][j-1])
print(C[len3-1][len2-1][len1-1])