문제

문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.

이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.

# 1958
import sys
input = lambda: sys.stdin.readline().strip()

string_A = list(input())
string_B = list(input())
string_C = list(input())

len_a, len_b, len_c = len(string_A), len(string_B), len(string_C)

LCS = [[[0] * (len_c + 1) for _ in range(len_b + 1)] for _ in range(len_a + 1)]

for a in range(len_a+1):
    for b in range(len_b+1):
        for c in range(len_c+1):
            if a == 0 or b == 0 or c == 0:
                LCS[a][b][c] = 0
            elif string_A[a-1] == string_B[b-1] == string_C[c-1]:
                LCS[a][b][c] = LCS[a-1][b-1][c-1] + 1
            else:
                LCS[a][b][c] = max(LCS[a-1][b][c], LCS[a][b-1][c], LCS[a][b][c-1])
                
len_lcs = 0
for a in range(1, len_a+1):
    for b in range(1, len_b+1):
        for c in range(1, len_c+1):
            len_lcs = max(len_lcs, LCS[a][b][c])
            
print(len_lcs)

LCS를 출력하는 프로그램

import sys
input = lambda: sys.stdin.readline().strip()

string_A = list(input())
string_B = list(input())
string_C = list(input())

len_a, len_b, len_c = len(string_A), len(string_B), len(string_C)

LCS = [[[0] * (len_c + 1) for _ in range(len_b + 1)] for _ in range(len_a + 1)]

for a in range(len_a+1):
    for b in range(len_b+1):
        for c in range(len_c+1):
            if a == 0 or b == 0 or c == 0:
                LCS[a][b][c] = 0
            elif string_A[a-1] == string_B[b-1] == string_C[c-1]:
                LCS[a][b][c] = LCS[a-1][b-1][c-1] + 1
            else:
                LCS[a][b][c] = max(LCS[a-1][b][c], LCS[a][b-1][c], LCS[a][b][c-1])
                
len_lcs = 0
ma, mb, mc = 0, 0, 0
for a in range(1, len_a+1):
    for b in range(1, len_b+1):
        for c in range(1, len_c+1):
            if LCS[a][b][c] > len_lcs:
                len_lcs = LCS[a][b][c]
                ma, mb, mc = a, b, c
            
print(len_lcs)
if len_lcs == 0:
    exit(0)

my_lcs = []
while ma > 0 and mb > 0 and mc > 0:
    if LCS[ma][mb][mc] == LCS[ma-1][mb][mc]:
        ma -= 1
    elif LCS[ma][mb][mc] == LCS[ma][mb-1][mc]:
        mb -= 1
    elif LCS[ma][mb][mc] == LCS[ma][mb][mc-1]:
        mc -= 1
    else:
        my_lcs.append(string_A[ma-1])
        ma, mb, mc = ma-1, mb-1, mc-1
        
for lcs in my_lcs[::-1]:
    print(lcs, end = "")

백준 1958 LCS 3