[Python/BOJ] 9251. LCS

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

9251번: LCS

문제

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

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

입력

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

출력

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

참고

https://oneul-hyeon.tistory.com/113

LCS(Longest Common Subsequence) 알고리즘

풀이

Code

import sys
input = sys.stdin.readline

string1, string2 = input().rstrip(), input().rstrip()
l1, l2 = len(string1)+1, len(string2)+1
# 1. LCS dp 생성
LCS = [[0] * l1 for _ in range(l2)]
# 2.
for i in range(1, l2) :
    for j in range(1, l1) :
        # 2-1. 문자가 같을 경우
        if string2[i-1] == string1[j-1] :
            LCS[i][j] = LCS[i-1][j-1] + 1
        # 2-2. 문자가 같지 않을 경우
        else :
            LCS[i][j] = max(LCS[i][j-1], LCS[i-1][j])
# 3. 결과 출력
print(LCS[-1][-1])