[BOJ/ Python] LCS || 다이나믹 프로그래밍

백준 LCS 파이썬 9251

9251번: LCS

 

❍ 문제

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

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

❍ 입력

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

❍ 출력

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

 

❏ 문제 풀이

이처럼 문자를 하나씩 늘려가며 비교하다가, A처럼 추가된 문자가 일치하는 경우를 살펴보자.
 

이는 A가 두 문자열이 추가되지 않았을 때에서 A가 추가된 것과 같다.
 

이처럼 비교할 때, 문자열이 일치하지 않은 경우를 살펴보자.
 

P만 추가되었을 경우와, K만 추가되었을 경우를 확인하여 둘 중에 더 긴 길이를 적용시켜주면 된다.
 

 
위와 같이 DP 리스트가 구성되게 된다.
추가된 문자가 동일할 경우, dp[i][j] = dp[i - 1][j - 1] + 1
동일하지 않은 경우, dp[i][j] = max(dp[i - 1][j], dp[i][j -1])
 

❍ CODE

import sys

input = sys.stdin.readline

a = input().strip()
b = input().strip()
dp = [[0 for _ in range(len(b) + 1)] for _ in range(len(a) + 1)]

for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        if a[i - 1] == b[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[-1][-1])