[백준/파이썬] 1958번 LCS 3 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 15734번 명장 남정훈
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

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

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

• 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요

코드

s1, s2, s3 = input(), input(), input()
dp = [[[0]*(len(s3)+1) for _ in range(len(s2)+1)] for _ 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])
m = 0
for matrix in dp:
    for row in matrix:
        m = max(m, max(row))
print(m)

설명

동적 프로그래밍을 응용하는 문제입니다.

우선, 문자열 3개를 s1, s2, s3 변수로 입력받습니다.

이후 메모이제이션에 사용할 dp변수를 선언합니다.

각 문자열의 길이가 마지막인덱스가 되도록 +1을 하여 3차원 리스트로 생성하였습니다.

이후는 단순히 모든 경우를 반복하며 현재의 dp리스트의 원소에 각 비교대상 문자가 같은가, 다른가에 따라 이전 dp리스트의 원소의 값을 참조하여 배정해줍니다.

이렇게 나온 3차원 리스트의 원소 중 가장 큰 값이 세 문자열의 LCS의 길이입니다.

 if s1[i-1] == s2[j-1] == s3[k-1]:
                dp[i][j][k] = dp[i-1][j-1][k-1]+1

위와 같은 조건인 이유는, 각 문자열의 공통문자열을 파악하기 위한 ‘시작점’을 어디로 잡았는가를 고려하기 위함입니다.

복잡도가 O(n^3)으로 상당히 큰 알고리즘이지만, 문자열의 길이 n이 모두 100이하로 작기 때문에, 최대 100,000번 반복하므로 시간 내에 풀 수 있습니다.

---

• 백준 문제풀이 전체 목록 보기

---