[Python] 백준9251 LCS

25 May 2023 in Study on Algorithm

백준9251 LCS 링크

문제

예제 입력

---

코드

import sys
input = sys.stdin.readline
a = input().strip()
b = input().strip()
h, w = len(a), len(b)
print(a)
print(b)

# dp알고리즘
dp = [[0] * (w+1) for _ in range(h+1)]
for i in range(1, h+1):
    for j in range(1, w+1):
        # 문자가 같으면 이전까지 길이 + 1
        # 한번에 ACAYKP와 CAPCAK의 최장 길이가 아닌 하나씩 같으면
        # AC와 CA의 최장 길이 + 1
        if a[i-1] == b[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        # 현재 글자(a[i-1])가 이전에 포함되냐 안돼냐 보면서 최장 길이 확인
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

print(dp[-1][-1])
# print(max(map(max, dp)))

설명

파이썬을 통해서 사용자로부터 입력받아 dp알고리즘을 사용하여 LCS를 정복 분할하여 구현했습니다.

---

결과