[BaekJoon] 1958 LCS 3 (Gold 3) - Python

문제

 

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

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

---

입출력 예시

 

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

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

 

입력예시1)

abcdefghijklmn
bdefg
efg

출력예시1)

3

---

코드

 

LCS문제는 DP로 푼다.

그 저어어어기 코드에 링크 적어놨는데, 들어가서 보면 진짜 정말 자세하게 설명되어 있다.

 

간단히 점화식부터 설명하자면,

if i == 0 or j == 0: LCS[i][j] = 0
elif string_a[i] == string_B[j]: LCS[i][j] = LCS[i - 1][j - 1] + 1
else: LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

이다.

 

맨 처음 라인은 마진, 즉 맨 앞의 쓸데없는 부분을 전부 0으로 설정한 것 이다

 

두 번재 라인은 두 문자가 같은 경우이다.

두 문자가 같은 경우, 해당 인덱스값을 대각선 앞의 인덱스 값에 +1을 한 값으로 저장한다.

 

세 번째 라인은 두 문자가 다른 경우이다.

두 문자가 다른 경우, 해당 인덱스 값의 수직으로 한 칸 앞, 즉 i - 1과 j - 1인덱스 중 더 큰 값으로 저장한다.

 

이 문제는 총 3개의 string의 LCS길이를 구하는 문제이므로 위 과정을 3차원 리스트로 변형하여 풀면 풀린다.

 

l_1 = list(input()) # 첫 번째 문자열 입력
l_2 = list(input()) # 두 번째 문자열 입력
l_3 = list(input())

# LCS알고리즘 참고
# https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

l_1 = ["-"] + l_1 # 문자열의 맨 앞에 더미데이터 추가
l_2 = ["-"] + l_2 # 문자열의 맨 앞에 더미데이터 추가
l_3 = ["-"] + l_3 # 문자열의 맨 앞에 더미데이터 추가

LCS = [[[0 for _ in range(len(l_3))] for _ in range(len(l_2))] for _ in range(len(l_1))] # LCS를 나타낼 3차원 배열 선언

for i in range(len(l_1)):
    for j in range(len(l_2)):
        for k in range(len(l_3)):
            if i == 0 or j == 0 or k == 0: LCS[i][j][k] = 0
            elif l_1[i] == l_2[j] and l_2[j] == l_3[k]: LCS[i][j][k] = LCS[i - 1][j - 1][k- 1] + 1
            else: LCS[i][j][k] = max(LCS[i - 1][j][k], LCS[i][j - 1][k], LCS[i][j][k - 1])

print(max(max(max(LCS)))) # 최대값 출력

---

실행 화면

 

---

채점 결과