[백준1958] LCS 3

 

www.acmicpc.net/problem/9251

9251번: LCS

개념

LCS는Longest Common Subsequence의 줄임말로,공통 부분 문자열 중 가장 길이가 긴 문자열을 말합니다.

이 때, Substring과 Subsequence와의 차이점을 알 필요가 있습니다.

 

• Substring : 전체 문자열에서연속된부분 문자열
• Subsequence : 전체 문자열에서꼭 연속된 문자열인 것은 아닌부분 문자열

서로 다른 문자열 중에서 공통 Subsequence를 찾는데,그 중길이가 가장 긴 Subsequence를 찾으려 하는 것입니다.

[예] ABCDEF 와 ACDGHI 와의공통 Subsequence 중 가장 길이가 긴 것은 ABCDEF /AZGCDGHI 에서ACD이다.

---

풀이

문자열 2개를 통한 LCS 알고리즘을 알아야 풀 수 있습니다.

문자열RBKBGRBG과, 문자열BGKRBRKB가 있다고 해 봅시다.

이런식으로 2차원 dp배열을 짜고 dp[i][j]에 가장 긴 LCS를 넣어줍니다.

차례대로 진행을 해나가다 보면 규칙성을 발견할 수 있습니다.

 

• 문자열을 비교하여 같았을 때 현재 칸에 들어갈 값은대각선 왼쪽 위의 값 + 1이다
• 문자열을 비교하여 달랐을 때 현재 칸에 들어갈 값은왼쪽과 위쪽의 값 중 더 큰 값이 들어간다.

기존에 풀이법을 알고 있지 않으면 DP는 이런식으로 규칙성을 찾아서 점화식을 만드는게 중요합니다

점화식은 위의 규칙을 활용하면

문자가 일치할 때

 

• dp[i][j] = dp[i-1][j-1] + 1

문자가 일치하지 않을 때

 

• dp[i][j] = max(dp[i-1][j],dp[i][j-1])

이라고 볼 수 있습니다.

LCS 3는 문자열을 3개로 늘렸을 뿐 규칙은 똑같습니다. 즉 아래와 같이 점화식이 만들어집니다.

문자가 일치할 때

 

• dp[i][j][k] = dp[i-1][j-1][k-1] + 1

문자가 일치하지 않을 때

 

• dp[i][j][k] = max(dp[i-1][j][k],dp[i][j-1][k],dp[i][j][k-1])

---

코드

s1 = input()
s2 = input()
s3 = input()

dp = [[[0 for i in range(101)] for j in range(101)] for k in range(101)]
n1,n2,n3 = len(s1),len(s2),len(s3)

for i in range(1,n1+1):
    for j in range(1,n2+1):
        for k in range(1,n3+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])
    
print(dp[n1][n2][n3])