[백준] 9251번 LCS

출처: [백준] 9251번 LCS

---

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

---

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

---

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

---

예제 입력 1

ACAYKP
CAPCAK

예제 출력 1

4

---

힌트

-

---

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: qpwoeiruty

---

알고리즘 분류

• 다이나믹 프로그래밍
• 문자열

---

풀이

-

---

소스코드

import sys

input = sys.stdin.readline

str1 = ' ' + input().rstrip()
str2 = ' ' + input().rstrip()

dp = [[0] * len(str2) for _ in range(len(str1))]

for i in range(1, len(str1)):
    for j in range(1, len(str2)):
        if str1[i] == str2[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

print(dp[-1][-1])