[Python] G5_9251_LCS 🔤🔤

https://www.acmicpc.net/problem/9251

문제

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

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

입력

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

출력

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

예제

코드

import sys
input = sys.stdin.readline

W1 = input().strip()
W2 = input().strip()

dp = [0]*1000 # LCS 길이 저장

for i in range(len(W1)):
    mx = 0
    for j in range(len(W2)):
        if mx < dp[j]: # 현재까지의 최대 길이로 갱신
            mx = dp[j]
        elif W1[i] == W2[j]:
            dp[j] = mx + 1 # LCS 길이 + 1
            
print(max(dp))

mx는 현재까지의 최대 길이로 계속해서 갱신해준다.

• 즉, 현재 인덱스까지의 최대 LCS 길이를 의미한다.

같은 부분 문자열을 발견하면, LCS 길이를 +1 해준다.

최종적으로 저장된 LCS 길이의 최댓값을 출력한다.

느낀 점 & 배운 점

1. dp문제에 굉장히 약하다는 것을 알게 된 문제.. 답을 보고 나면 정말 간단한 데 떠올리기가 어려운 것 같다ㅜ 아직 많은 연습이 필요할 것 같다!