[백준/Python] 1958 LCS 3

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

1958번: LCS 3

문제 분석

난이도

골드 3

분류

LCS, DP

들어가기 전에

앞서 LCS 문제들을 풀고오지 않았다면 더 어려울 수 있다.

문제

 

문제 풀이

 

풀이

기존 LCS코드에(2중 for문)에 한 줄을 더 늘려주면 된다. 그렇게 되면 3개가 같을 경우 +1이 되므로 사실 2개일 때랑 별 차이가 없는 문제이다. (4개라면 4중, 5개라면 5중으로 굴려주면 될 것이다. 시간복잡도가 N^5인 것만 감안하면..!)

소스코드

 

def getLcs(s1,s2,s3):
    dp=[[[0]*(len(s3)+1) for i in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(1,len(s1)+1):
        for j in range(1,len(s2)+1):
            for k in range(1,len(s3)+1):
                if s1[i-1]==s2[j-1]==s3[k-1]:
                    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])
    return dp[-1][-1][-1]
print(getLcs(input(),input(),input()))