[DP] 백준 1958번 “LCS 3” Python 풀이

문제 링크

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

풀이

• 2차원 DP 테이블을 사용한 LCS 문제와 동일한 방식으로, 3차원 DP 테이블을 사용해서 해결할 수 있습니다.
  • 기본적인 LCS 알고리즘은 해당 포스트에선 생략하겠습니다.
• 코드 작성은 쉬울 수 있으나, 시각적으로는 잘 그려지지 않는 것 같습니다.

코드

import sys

# 각 문자열 입력
first = sys.stdin.readline().rstrip()
second = sys.stdin.readline().rstrip()
third = sys.stdin.readline().rstrip()

# DP 테이블 초기화
dp = [[[0] * (len(third)+1) for _ in range(len(second)+1)] for _ in range(len(first)+1)]

# LCS 진행
for i in range(1, len(first)+1):
    for j in range(1, len(second)+1):
        for k in range(1, len(third)+1):

            # 3개의 문자가 같을 경우
            if (first[i-1] == second[j-1] == third[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[len(first)][len(second)][len(third)])