[백준][파이썬][DP][LCS] 1958번: LCS3

문제집: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

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

 

이전 문제:

LCS https://hyundoil.tistory.com/357

LCS2 https://hyundoil.tistory.com/369

LCS 문제 모음 : https://www.acmicpc.net/workbook/view/5080

문제

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

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

입력

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

출력

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

 

예제 입력 1

abcdefghijklmn
bdefg
efg

예제 출력 1

3

 

---

 

문자가 3개라서 다른 특별한 방법이 있는게 아니고 3중for문 돌리면 된다.    

 

def solution(word1, word2, word3):
    N = len(word1)
    M = len(word2)
    L = len(word3)
    
    # DP 테이블 초기화
    dp = [[[''] * (L + 1) for _ in range(M + 1)] for _ in range(N + 1)]
    
    # DP 테이블 채우기
    for i in range(1, N + 1):
        for j in range(1, M + 1):
            for k in range(1, L + 1):
                if word1[i - 1] == word2[j - 1] == word3[k - 1]:
                    dp[i][j][k] = dp[i - 1][j - 1][k - 1] + word1[i - 1]
                else:
                    if len(dp[i - 1][j][k]) >= len(dp[i][j - 1][k]) and len(dp[i - 1][j][k]) >= len(dp[i][j][k - 1]):
                        dp[i][j][k] = dp[i - 1][j][k]
                    elif len(dp[i][j - 1][k]) >= len(dp[i][j][k - 1]):
                        dp[i][j][k] = dp[i][j - 1][k]
                    else:
                        dp[i][j][k] = dp[i][j][k - 1]
    
    # LCS 길이 출력
    answer = len(dp[N][M][L])
    print(answer)
    

if __name__ == "__main__":
    word1 = input().strip()
    word2 = input().strip()
    word3 = input().strip()
    
    solution(word1, word2, word3)