백준 9251번 바로가기

나의 풀이

# 입력
import sys

read = sys.stdin.readline

A, B = read().strip(), read().strip()
n, m = len(A), len(B)
LCS = [[0] * (m + 1) for _ in range(n + 1)]

# 처리 - LCS 알고리즘 이용
for i in range(1, n + 1):
  for j in range(1, m + 1):
    if A[i - 1] == B[j - 1]:
      LCS[i][j] = LCS[i - 1][j - 1] + 1
    else:
      LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

print(LCS[n][m])

CODE REVIEW

  1. 백준 17218번 문제에서 배운 LCS 알고리즘을 이용한 문제.
  2. 17218번은 이 문제의 문자열 ver. 변형이라고 볼 수 있다.
  3. (n*m) matrix에 경로찾기처럼 숫자를 더해나가며 채워가면 최장 공통 부분 수열의 최대 길이는 마지막 요소에 저장된다.

REFERENCES