[Baekjoon] 9251 LCS

문제

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

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

 

원본

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

 

풀이<\/b><\/h2>

import sys
input = sys.stdin.readline

a = list(input())
b = list(input())

arr = [[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]:
            arr[i][j] = arr[i-1][j-1] + 1
        else:
            arr[i][j] = max(arr[i-1][j], arr[i][j-1])
            
print(max(map(max,arr)))