[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 1958번 _ LCS 3

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

1958번: LCS 3

[문제]

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

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

 

[입력]

첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다.

[출력]

첫 줄에 첫 번째 문자열과 두 번째 문자열과 세 번째 문자열의 LCS의 길이를 출력한다.

 

[아이디어]

1) 문자열 2개의 LCS와 기본적으로 동일하다.

2) dp 문제이며, 특정 위치의 문자열이 모두 같아 그것을 포함해 LCS가 형성되는 경우와, 그렇지 않은 경우로 subproblem을 구성할 수 있다.

3) 세 문자열의 인덱스 i,j,k에 대하여, 해당 위치의 문자열이 셋 다 같다면, "dp[i][j][k] = dp[i-1][j-1][k-1]+1" 이고, 같지 않다면 dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1]의 값 중 최대의 값을 가져야한다.

 

s1=' '+ input()
s2=' '+ input()
s3=' '+ input()
a=len(s1)
b=len(s2)
c=len(s3)
dp = [[[0]*(c) for _ in range(b)] for _ in range(a)]
for i in range(1,a):
    for j in range(1,b):
        for k in range(1,c):
            if s1[i]==s2[j]==s3[k]:
                dp[i][j][k] = dp[i-1][j-1][k-1]+1
            else:
                dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])
print(dp[-1][-1][-1])