(파이썬 python) 백준 9251번 : LCS

LCS는 임의의 두 문자열에서 가장 긴 subsequence의 길이를 구하는 문제다.

처음 접해보는 개념이라 2시간정도 혼자서 고민하다가 다른 사람의 정리된 블로그를 보면서 이해하였다.

 

이미 만들어 놓은 결과위에 새로운 문제들을 이어서 푼다는 DP의 특징을 기억하고 있을 필요가 있다.

---

 

 

위의 표에서 (2,3), (2,6), (3,2), (3,5), (4,3), (4,6), (6,7)은 모두 행과 열의 문자가 같다.

이렇게 행과 열의 문자가 같은 셀의 값은 왼쪽 대각선 위에 있는 수에서 1을 더한 값이 되는 규칙을 찾을 수 있다.

 

1. 각각의 문자열에서 가장 최근에 추가된 문자가 같을 경우

왼쪽 대각선 위의 셀에서 각각 같은 문자열이 추가되었으므로 +1을 해준다.

예)

(3,5)셀 : CAP와 A에서 C가 공통적으로 추가되어 CAPC, AC로 LCS는 AC가 된다.

(4,6)셀 : CAPC와 AC에서 A가 공통적으로 추가되어 CAPCA, ACA로 LCS 는 ACA가 된다.

 

 

2. 각각의 문자열에서 가장 최근에 추가된 문자가 다른 경우

LCS는 연속적인 부분수열일 필요가 없으므로 기존의 문자열에서 만들 수 있던 LCS중  최대 길이의 LCS 값을 갖게 된다.

예)

(3,3)셀 : CAP와 AC 인 경우는 1, CA와 ACA인 경우는 2로 각각이 만들 수 있는 LCS중 큰 값이 LCS값이 된다.

 

아래 코드가 위의 규칙을 구현한 것이다.

import sys

S1 = sys.stdin.readline().strip().upper()
S2 = sys.stdin.readline().strip().upper()
len1 = len(S1)
len2 = len(S2)
matrix = [[0] * (len2 + 1) for _ in range(len1 + 1)]

for i in range(1, len1 + 1):
    for j in range(1, len2 + 1):
        if S1[i - 1] == S2[j - 1]:
            matrix[i][j] = matrix[i - 1][j - 1] + 1
        else:
            matrix[i][j] = max(matrix[i - 1][j], matrix[i][j - 1])

print(matrix[-1][-1])

---

참고한 블로그

출처: https://suri78.tistory.com/11 [공부노트:티스토리]