백준|9251번|LCS

문제 설명

두 문자열을 입력받고 두 문자열의 최장 공통 부분 수열(LCS)을 출력하는 문제입니다.

작동 순서

1. 두 문자열 A, B를 입력받습니다.
2. 두 문자열의 위치에서 LCS의 길이를 저장하는 2차원 배열 dp를 생성합니다.
3. A의 문자와 B의 문자를 하나씩 비교해가며 A의 문자와 B의 문자가 같은 경우 이전 LCS 길이에서 +1을 해줍니다.
4. A의 문자와 B의 문자의 길이가 다른 경우 이전 LCS 길이 중 가장 긴 LCS 값을 저장합니다.
5. A 문자열과 B 문자열을 모두 비교한 뒤 가장 긴 LCS의 길이를 출력합니다.

소스코드

import sys
A = "0"+sys.stdin.readline().rstrip()
B = "0"+sys.stdin.readline().rstrip()

dp = [[0 for _ in range(len(B))] for _ in range(len(A))]
lcs = 0

for a in range(1, len(A)):
    for b in range(1, len(B)):
        if A[a] == B[b]:
            dp[a][b] = dp[a-1][b-1]+1
            if lcs < dp[a][b]:
                lcs = dp[a][b]
        else:
            dp[a][b] = max(dp[a-1][b], dp[a][b-1])
print(lcs)