백준 9251번: LCS (Python)

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

 

---

 

풀이

dp[i][j]: A의 i번째 글자까지, B의 j번째 글자까지 비교했을 때의 LCS라고 하자. 그러면 dp는 len(A)+1 by len(B)+1 행렬이 되야 할 것이다.

자명하게도 dp[i][j] == 0 when i == 0 or j == 0이 되며, 이제 i, j에 대해서 1부터 len(A), len(B)까지 for문을 돈다.

만약 i번째 글자랑 j번째 글자랑 같다면, 이는 LCS의 일부분이 될 수 밖에 없으며(개인적으로, 이 문제도 LIS랑 관련이 있는 줄 알고 이 발견을 못했다.) 따라서 dp[i][j] = 1 + dp[i-1][j-1]이다.

만약 i번째 글자랑 j번째 글자랑 다르다면, dp[i][j] = max(dp[i-1][j], dp[i][j-1])이다.

아이디어 출처: https://happylsm76.tistory.com/entry/%EB%B0%B1%EC%A4%80-9251%EB%B2%88LCS-with-Python

 

---

 

코드

import sys

A = sys.stdin.readline().strip().upper()
B = sys.stdin.readline().strip().upper()
dp = [[0]*(len(B)+1) for _ in range(len(A)+1)]

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

print(dp[-1][-1])