[백준] 1958번 - LCS 3 / 골드 3 / 파이썬 풀이

문제 링크

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

1958번: LCS 3

 

시간 제한 : 2초

메모리 제한 : 128 MB

 

문제 요약

• LCS(Longest Common Subsequence) : 최장 공통부분 수열. 주어진 여러개의 수열 모두의 부분수열이 되는 수열들 중 가장 긴 것.
  

  

  최장 공통 부분수열(Longest Common Subsequence)와 최장 공통 문자열(Longest Common Substring)의 차이

  
  
  
• 문제 : 문자열 3개의 LCS(Longest Common Subsequence)의 길이를 출력하여라.
  
  

입력

예제 입력 1

abcdefghijklmn
bdefg
efg

 

출력

예제 출력 1

3

---

풀이

"세 문자열의 문자를 하나하나 차례대로 모두 비교하고, 문자가 동일하다면 해당 인덱스에는 이전까지 기록된 최장 길이값에 +1을 하자!"

import sys

input = sys.stdin.readline

seq_1 = input().rstrip()  # rstrip() : 문자열 오른쪽의 공백 제거.
seq_2 = input().rstrip()
seq_3 = input().rstrip()

x = len(seq_1)
y = len(seq_2)
z = len(seq_3)

# 문자열 길이의 +1을 해주는 이유는, 이전 인덱스의 값과 비교해야 하기 때문이다.
arr = [[[0] * (z + 1) for _ in range(y + 1)] for _ in range(x + 1)]

for i in range(1, x + 1):
    for j in range(1, y + 1):
        for k in range(1, z + 1):
            if seq_1[i - 1] == seq_2[j - 1] and seq_2[j - 1] == seq_3[k - 1]:
                arr[i][j][k] = arr[i - 1][j - 1][k - 1] + 1

            else:
                # 세 문자열의 문자끼리 비교하였을 때 같지 않다면, 이전까지 기록된 가장 긴 최장 수열의 값을 기록하여 최신화한다.
                arr[i][j][k] = max(arr[i][j][k - 1], arr[i][j - 1][k], arr[i - 1][j][k])

ans = -1

for i in range(x + 1):
    for j in range(y + 1):
        ans = max(max(arr[i][j]), ans)

print(ans)

 

참고

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

1958번: LCS 3

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence