[백준] 9251번(LCS) with Python

문제

www.acmicpc.net/problem/9251

9251번: LCS

풀이

먼저 LCS(Longest Common Subsequence, 최장 공통 부분 수열)는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 부분을 말한다.

예시로 ACAYKP와 CAPCAK를 이용해 표를 그려보았다.

ACAYKP를 비교 대상으로 잡고 CAPCAK 문자열 하나씩 추가하면서 공통 수열 길이 값을 표시해준다.

 

 

위와 같이 반복을 하다보면 규칙을 찾을 수 있다.

행은 이전 행의 값과 같고, 같은 문자가 나오는 경우 이전 값에 +1을 하고 있는 것을 알 수 있다.

최종으로 작성된 표는 이렇게 나오게 된다. 즉, LSC는 4라는 것을 알 수 있다.

답

import sys

A = sys.stdin.readline().strip().upper()
B = sys.stdin.readline().strip().upper()

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 :
      lcs[i][j] = max(lcs[i][j-1], lcs[i-1][j])

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