[DP] 1958번 - LCS3 (9일차)

#첫번째 문자열 입력
l1 = input()
#두번째 문자열 입력
l2 = input()
#세번째 문자열 입력
l3 = input()

#첫번째 문자열의 길이
len1 = len(l1)
#두번째 문자열의 길이
len2 = len(l2)
#세번째 문자열의 길이
len3 = len(l3)

#dp = 해당 지점까지의 가장 긴 공통 부분 수열의 길이를 저장
#단, i,j,k가 각각 0일때 dp의 값을 0으로 미리 채움 (인덱스 에러 방지용)
dp = [[[0 for _ in range(len3+1)] for _ in range(len2+1)] for _ in range(len1+1)]

#i(l1의 각 문자)를 중심으로
for i in range(1,len1+1):

    #j(l2 각 문자)에 대해 탐색
    for j in range(1,len2+1):
        #k(l3 각 문자)에 대해 탐색
        for k in range(1,len3+1):
            #ㅣ1의 문자와 l2의 문자와 l3의 문자가 같을 때
            if(l1[i-1] == l2[j-1] == l3[k-1]):
                #dp[i-1][j][k] = l1의 직전 문자, l2의 해당 인덱스, l3의 해당 인덱스까지 최고 수열
                #dp[i-1][j-1][k] = l1의 직전 문자, l2의 직전 인덱스, l3의 해당 인덱스까지 최고 수열
                #dp[i-1][j][k-1] = l1의 직전 문자, l2의 해당 인덱스, l3의 직전 인덱스까지 최고 수열에 길이를 더함
                #dp[i][j-1][k] = l1의 해당 문자, l2의 직전 인덱스, l3의 해당 인덱스까지 최고 수열
                #dp[i][j-1][k-1] = l1의 해당 문자, l2의 직전 인덱스, l3의 직전 인덱스까지 최고 수열
                #dp[i][j][k-1] = l1의 해당 문자, l2의 해당 인덱스, l3의 직전 인덱스까지 최고 수열
                #dp[i-1][j-1][k-1]+1 = l1의 직전 문자, l2의 직전 인덱스, l3의 직전 인덱스까지 최고 수열의 길이에 1을 더함
                dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k], dp[i-1][j][k-1], dp[i][j-1][k], dp[i][j-1][k-1], dp[i][j][k-1], dp[i-1][j-1][k-1]+1)

            else:
                #dp[i-1][j][k] = l1의 직전 문자, l2의 해당 인덱스, l3의 해당 인덱스까지 최고 수열
                #dp[i-1][j-1][k] = l1의 직전 문자, l2의 직전 인덱스, l3의 해당 인덱스까지 최고 수열
                #dp[i-1][j][k-1] = l1의 직전 문자, l2의 해당 인덱스, l3의 직전 인덱스까지 최고 수열에 길이를 더함
                #dp[i][j-1][k] = l1의 해당 문자, l2의 직전 인덱스, l3의 해당 인덱스까지 최고 수열
                #dp[i][j-1][k-1] = l1의 해당 문자, l2의 직전 인덱스, l3의 직전 인덱스까지 최고 수열
                #dp[i][j][k-1] = l1의 해당 문자, l2의 해당 인덱스, l3의 직전 인덱스까지 최고 수열
                dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k], dp[i-1][j][k-1], dp[i][j-1][k], dp[i][j-1][k-1], dp[i][j][k-1])

#l1과 l2과 l3를 끝까지 탐색한 상황에서 가장 긴 수열 길이 출력
print(dp[-1][-1][-1])

#인사이트
#l1과 l2에서 LCS를 구하고, l3와 LCS를 구하는 것은 1차 LCS가 l1과 l2의 최대 교집합으로 이루어져 l3와 존재할 수 있는 최대 교집합을 누락할 수 있음
#따라서 DP를 3차원 리스트로 선언해 n^3의 탐색을 통해 l1,l2,l3을 동시에 비교해줘야 함
#35,44줄에 쓰인 max 안의 다양한 케이스들은 결국 dp[i][j][k]를 중심으로 3방향에서 접근하며 탐색한다는 의미
#이때, 접근하는 경우의 수는 리스트의 차원 n 기준 2^n-2로 3차원의 경우 높이, 가로, 세로 측면에서 탐색한다고 볼 수 있음 -> 4,5차원에서도 활용 가능
#[i-1][j-1][k-1]에 1을 더하는 이유는 해당 인덱스가 [i][j][k]의 인덱스가 반영되지 않은 상태의 최고 수열 길이가 보관되어 있기 때문