백준 9251 | LCS (다이나믹 프로그래밍) | 파이썬

문제 출처 : https://www.acmicpc.net/problem/9251

문제

• LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제는 두 수열이 주어졌을 때,
  모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
• 두 문자열이 주어진다. 두 문자열의 LCS의 길이를 출력하시오.

문제 접근 방법

• 동적 계획법의 문제들은 점화식을 찾기가 상당히 어려운 것 같다.
• 이 문제를 풀면서 느낀 점은

점화식을 찾기 어렵다면
어떻게 DP or Memoization 테이블을 만들면 좋을지 생각해보고
문제에서 주어진 예시 OR 테스트 케이스를 직접 그려본 다음
규칙성을 통해 점화식을 찾아야 한다.

• 점화식을 찾는 것이 어렵지만, 점화식을 찾았다면 그대로 구현만 하면 된다.

코드

import sys

input = sys.stdin.readline

A = input().rstrip()
B = input().rstrip()

lcs = [[0] * (len(A) + 1) for _ in range(len(B) + 1)]

for i in range(1, len(B) + 1):
    for j in range(1, len(A) + 1):
        if B[i-1] == A[j-1]:
            lcs[i][j] = lcs[i-1][j-1] + 1
        else:
            d[i][j] = max(lcs[i-1][j], lcs[i][j-1])

print(lcs[-1][-1])