📌 [BOJ] 백준 9251 LCS

📖 문제

📖 예제

📖 풀이

A = list(input())
B = list(input())

dp = [0] * len(B)

for i in A:
  cnt = 0
  for j in range(len(B)):
    if cnt < dp[j]:
      cnt = dp[j]
    elif i == B[j]:
      dp[j] = cnt + 1
print(max(dp))

가장 긴 수열을 찾는 문제로 다이나믹 프로그래밍의 대표적인 문제 중 하나이다.
for 문의 동작 방식은 다음 그림과 같다.