[백준/Python] 9251번 - LCS

문제

백준 9251번 - LCS

해결 과정

• DP를 이용한 LCS
• LCS는 2차원 배열로, 행과 열을 두 문자열의 길이로 설정하며 모든 값을 0으로 초기화
• 문자열을 하나씩 비교하는데
  문자열이 같다면 지금까지 최대 공통 부분수열 + 1
  문자열이 다르다면 그 이전 과정에서 큰 값을 넣는다.
• ex) ABCDEF / GBCDFE
  A vs. G,GB,GBC,GBCD,GBCDF,GBCDFE
  AB vs. G,GB,GBC,GBCD,GBCDF,GBCDFE
  ABC vs. G,GB,GBC,GBCD,GBCDF,GBCDFE

풀이

import sys

strA = sys.stdin.readline().strip()
strB = sys.stdin.readline().strip()

n = len(strA)
m = len(strB)

LCS = [[0] * (m+1) for _ in range(n+1)]

for i in range(1,n+1):
  for j in range(1,m+1):
    if strA[i-1] == strB[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[-1][-1])