100년 뒤 개발자 한승규입니다.

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

옛날에 굉장히 고생했었던 LCS이다.

그 기억 때문에 이번 동적 프로그래밍에서 이번 문제를 뽑은 거 같기도 하다.

당연히 동적 프로그래밍답게 배열이 등장한다.

하지만 여기서는 기존과는 다르게 2차원 배열이다.

이 생각을 못해서 옛날에 굉장히 고생했었다.

일단 이런 식의 배열을 생성한다.

구하는 방식은 ACAYKP로 문자열을 기준 잡고

C, CA, CAP, CAPC, CAPCA, CAPACK를 순서대로 비교해가며 가장 긴 공통 수열을 찾아가는 방식이다.

각 문자열의 가장 앞에는 빈 문자열을 둔 것이고, 당연히 빈 문자열이기 때문에 공통 수열의 길이는 0이다.

우선 C부터 비교를 해보자

가장 긴 공통 수열은 C 하나 일 것이다.

그러면 ACAYKP에서 C 이후로는 가장 긴 공통 수열의 길이가 1이 될 것이다.

그 후로는 A를 비교해본다.

현재 비교하는 문자열은 CA이다.

ACA 이후로는 CA가 겹치기 때문에 가장 긴 공통 수열의 길이는 2가 된다.

마지막으로 CAP까지만 비교해보자.

CAP가 겹치기 때문에 길이는 3이 나오게 된다.

여기서 배열은

만약 해당 문자가 같을 경우(first_word[i] == second_word[t])에는 dp[i][t] = dp[i-1][t-1] + 1을 저장해주고

만약 해당 문자가 다른 경우(first_word[i] != second_word[t])에는 do[i][t] = max(dp[i][t-1], dp[i-1][t])로 저장해주면 된다.

그렇게 만들어진 최종 배열이다.

만들어진 코드는 다음과 같다.

import sys

first_word = list(sys.stdin.readline().strip())
second_word = list(sys.stdin.readline().strip())

max_length = max(len(first_word), len(second_word))

dp = [[0 for i in range(max_length + 1)] for t in range(max_length + 1)]

for i in range(len(first_word)):
    for t in range(len(second_word)):
        if first_word[i] == second_word[t]:
            dp[i][t] = dp[i-1][t-1] + 1
        else:
            dp[i][t] = max(dp[i][t-1], dp[i-1][t])


print(dp[len(first_word) - 1][len(second_word) - 1])