[백준] 1958번 LCS 3 - 파이썬 (Python)

문제 (링크)

 

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

1958번: LCS 3

 

나의 풀이

import sys
input = sys.stdin.readline

seq_1 = input().rstrip()
seq_2 = input().rstrip()
seq_3 = input().rstrip()

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

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)

코드 설명 및 풀이

기존 LCS가 두 개의 수열을 갖고 진행했다면, 이번 문제는 3개의 수열에 대한 LCS를 구해야했다.

 

기존 2차원 배열을 3차원으로 늘려주고 3중 for문을 사용해 해결할 수 있는 문제였다.

 

3차원 배열 자체가 익숙하지 않아서 머리 속에 쉽게 그려지진 않았지만, 코드 자체를 구현하는데는 어려움이 없었다.