BOJ 9251 LCS

문제

접근 방법

다이나믹 프로그래밍을 배울 때 보는 LCS 알고리즘을 그대로 적용하면 된다.

dp 배열에는 현재 위치까지 구한 가장 긴 부분 수열의 길이가 들어간다. 따라서, 같은 글자가 생기면 이전까지 구한 가장 긴 부분 수열의 길이에 1을 더하고 같은 글자가 안 생긴다면 이전까지 구한 가장 긴 부분 수열의 길이를 그대로 저장하면 된다.

풀이 코드

import sys
input = sys.stdin.readline

s1 = [' ']+list(input().rstrip())
s2 = [' ']+list(input().rstrip())
f_len = len(s1)
s_len = len(s2)
i = 0
j = 0

lcs = [[0]*(f_len) for _ in range(s_len)]

for i in range(1,f_len):
  for j in range(1, s_len):
    if s1[i] == s2[j]:
      lcs[j][i] = lcs[j-1][i-1]+1
    else:
      lcs[j][i] = max(lcs[j-1][i], lcs[j][i-1])


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