[백준/파이썬] 9251 LCS

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

---

알고리즘 분류

• 다이나믹 프로그래밍

문제풀이

백준 11053 문제와 유사한 문제이다.
너무 어렵다..

차근차근 예시를 살펴보자.
A C 0
A CA 1
A CAP 1
A CAPC 1...

AC C 1
AC CA 1
AC CAP 1
AC CAPC 2...

다음을 표로 나타내면 다음과 같다.

참고: https://suri78.tistory.com/11

AC CAPC 처럼 마지막에 넣은 알파벳이 같을 경우 두 알파벳이 추가되기 전인 A CAP의 길이 + 1로 나타낸다.

같지 않다면,(ACA CAPCAK) ACA CAPCA의 길이, AC CAPCAK의 길이 중 최대 길이로 나타낸다.(기존에 존재했던 문자열로 만들 수 있던 최대 길이를 가짐)

소스코드

a=input()
b=input()

d=[[0]*(len(b)+1) for _ in range(len(a)+1)]

for i in range(1,len(a)+1):
  for j in range(1,len(b)+1):
    if a[i-1]==b[j-1]:
      d[i][j]=d[i-1][j-1]+1 #두 글자가 추가되기 전 가장 큰 길이+1
    else:
      d[i][j]=max(d[i][j-1], d[i-1][j])

print(d[len(a)][len(b)])