[BOJ] 1958 - LCS 3 (Python)

 

 

아이디어

 

동적 계획법으로 세 문자열의 최장 공통 부분 열의 길이를 찾아 나간다.

 

LCS는 Longest Common Subsequence의 약자이기도 하고, Longest Common Substring의 약자이기도 하다.

부분 열(Subsequence)은 어떤 열의 요소들을 원래 순서에 따라 그 일부를 나열한 것이고,

부분 문자열(Substring)은 어떤 문자열 내에 포함된 연속적인 문자열을 의미한다.

 

따라서 최장 공통 부분 열과 최장 공통 부분 문자열은 공통 부분 요소들의 연속성에 차이가 있다.

부분 열은 연속되지 않은 요소들로도 구성할 수 있지만, 부분 문자열은 연속된 요소들로 구성된다.

 

이 문제에서는 각 문자열에서 일부 문자들을 순서대로 나열한 문자열 중 가장 긴 공통 문자열의 길이를 찾아야 한다.

 

 

풀이

 

세 문자열을 각각 S1, S2, S3에 저장하고, 그 길이를 각각 N1, N2, N3에 저장한다.

0으로 채워진 (N1+1)×(N2+1)×(N3+1) 크기의 3차원 리스트 dp를 생성하는데,

이후 인덱스 접근을 편리하게 하기 위해 각 문자열 길이보다 1씩 더 큰 길이로 만든다.

dp[i+1][j+1][k+1]에는 S1의 i 번째 문자, S2의 j 번째 문자, S3의 k 번째 문자까지의 최장 공통 부분 열 길이를 저장한다.

 

S1, S2, S3의 문자가 모두 같을 때 해당 문자들 이전까지의 최장 공통 부분 열 길이보다 1 더 큰 값을 저장하고,

그렇지 않으면 현재까지 저장된 부분 열의 길이 중 가장 긴 부분 열의 길이를 저장해 나간다.

 

def solution():
    S1, S2, S3 = input(), input(), input()
    N1, N2, N3 = map(len, [S1, S2, S3])
    dp = [[[0]*(N3+1) for _ in range(N2+1)] for _ in range(N1+1)]
    for i in range(N1):
        for j in range(N2):
            for k in range(N3):
                if S1[i] == S2[j] == S3[k]:
                    dp[i+1][j+1][k+1] = dp[i][j][k]+1
                else:
                    dp[i+1][j+1][k+1] = max(dp[i][j+1][k+1], dp[i+1][j][k+1], dp[i+1][j+1][k])
    print(dp[-1][-1][-1])

solution()