1958. LCS 3

LCS를 아시는 분 또는 9251. LCS 문제를 푸신 분들만 이 글을 읽으시기 바랍니다. 

---

문자열 3개의 Longest Common Subsequence를 구하는 문제이다. Substring이 아님에 주의하자.

---

문자열 2개의 LCS는 DP를 적용하여 해결할 수 있다. 두 문자열 A와 B에 대해 다음과 같이 정의되는 dp 배열을 채우면 A와 B의 LCS와 그 길이를 구할 수 있다.

if A[i] == B[j]:
    dp[i][j] = dp[i - 1][j - 1] + 1
else:
    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

 

풀어서 설명해 보면 다음과 같다. 이것이 왜 성립하는지는 알고 있을 것이다.

1) A[i] == B[j] → (LCS의 길이) = (i와 j 이전까지의 LCS의 길이) + 1

2) A[i] != B[j] → (LCS의 길이) = max(i 또는 j를 제외한 LCS의 최댓값)

 

---

 

이 식을 문자열 3개에 대해 확장하는 것은 어렵지 않다. 세 문자열 A, B, C에 대해 dp 배열을 다음과 같이 채우면 LCS의 길이를 구할 수 있다. LCS도 구할 수 있다. 

if A[i] == B[j] == C[k]:
    dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1
else:
    dp[i][j][k] = max(dp[i][j][k - 1], dp[i][j - 1][k], dp[i - 1][j][k])

 

---

사실.. 낮에 2시간동안 생각하다가 안 돼서 때려쳤는데, 알바하다가 생각난 것을 밤에 잠깐 코딩해서 제출하니까 맞았다. 조금 당황스러웠다. ㅋㅋ