9251번: LCS

import sys
input = sys.stdin.readline

words = []

for _ in range(2):
  words.append(list(map(str,input().rstrip())))

a = len(words[0])
b = len(words[1])

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

for i in range(1,a+1):
  for j in range(1,b+1):
    if words[0][i-1] == words[1][j-1]:
      dp[i][j] = dp[i-1][j-1] + 1
    else:
      dp[i][j] = max(dp[i-1][j],dp[i][j-1])

print(dp[a][b])

동적 계획법의 가장 기본이지 대표 문제인 최장 공통 부분 수열이다.

먼저 리스트 words에 두 문자열을 rstrip을 이용해 한 단어씩 받아준다.

그 후 두 단어의 문자열 길이를 a, b에 넣어주고 리스트 dp에 (b+1)개의 0을 갖는 리스트를 (a+1)개 만들어준다.

이런식으로 리스트를 만들면 2중 반복문을 통해 dp 리스트안에 있는 리스트 요소들 속 0을 모두 공통부분수열로 만들 수 있다.

2중 반복문 속에 if 문을 이용해 words의 0번째 index속 i-1 과 1번째 index 속 j-1 이 같다면
dp[i][j] = dp[i-1][j-1] + 1
즉 직전 최댓값에 +1 을 해주면 된다.
else 라면 dp[i][j] = max(dp[i][j-1],dp[i-1][j]) 를 통해 최댓값을 부여한다.

가장 마지막 값인 dp[a][b]를 출력하면 최댓값을 받을 수 있다.