[Baekjoon/python] LCS #9251

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

9251번: LCS

문제

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

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

코드

• DP 문제
• 두 문자의 길이가 다를 경우 2중 for문에서 짧은 문자가 먼저 나와야한다. 반례는 다음과 같다.
  • qsdferrfgtfsawfsefeesgdtdrgthyytfgfddsdawdwd
  • efvs
  • 답: 3

import sys

input = sys.stdin.readline

words = [input().strip(), input().strip()]
words.sort(key=len)

l1, l2 = len(words[0]), len(words[1])
cache = [[0] * (l2 + 1) for _ in range(l1 + 1)]

for i in range(1, l1 + 1):
    for j in range(1, l2 + 1):
        # character가 일치하면 이전 LCS + 1
        if words[0][i - 1] == words[1][j - 1]:
            cache[i][j] = cache[i - 1][j - 1] + 1
        # 이전 cache의 최댓값 유지
        else:
            cache[i][j] = max(cache[i][j - 1], cache[i - 1][j])

print(cache[-1][-1])