[백준] 1958 파이썬

문제

---

• 백준 1958 (골드 4)

백준 1958

3개의 문자열이 주어졌을 때, 3개의 문자열 중에서 가장 긴 부분 문자열의 길이를 구하는 문제였다.
문자열의 길이는 100보다 작거나 같다.

내 코드

---

처음에는 문제를 잘못 이해해서 이어진 부분 문자열만 가능하다고 생각해 잘못 구현하였다.
문제를 다시 이해하고 dp를 활용하여서 구현하였다.
3가지 문자열을 모두 순환하며 각각의 모든 문자를 비교하면서 문자가 같다면 이전의 dp를 활용하여서 해당 인덱스의 dp 테이블을 업데이트해주는 방식으로 구현하였다.

import sys
input = sys.stdin.readline

arr = [input().strip() for _ in range(3)]
dp = [[[0] * (len(arr[2]) + 1) for _ in range(len(arr[1]) + 1)] for _ in range(len(arr[0]) + 1)]
ans = 0

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

for i in range(1, len(arr[0]) + 1):
    for j in range(1, len(arr[1]) + 1):
        for k in range(1, len(arr[2]) + 1):
            ans = max(ans, dp[i][j][k])

print(ans)

3중 리스트는 조금 익숙치 않지만 적절하게 잘 활용해 보아야겠다.