[백준/Python] LCS

https://www.acmicpc.net/problem/9251

 

참고: 

https://osnim.tistory.com/entry/%EC%B5%9C%EC%9E%A5-%EA%B3%B5%ED%86%B5-%EB%B6%80%EB%B6%84%EC%88%98%EC%97%B4-LCSLongest-Common-Subsequence-%ED%8C%8C%EC%9D%B4%EC%8D%AC

최장 공통 부분수열, LCS(Longest Common Subsequence) (파이썬)

---

DP를 이용

LCS의 점화식 구하기

 

예시1)

문자열 1: ACP
문자열 2: CAP

DP[N][M]을 구해야 합니다.

 

맨 뒤의 두 문자 비교(P와 P)

두 문자가 동일하면 -> +1

그 앞의 문자열을 비교(AC와 CA) -> DP[N-1][M-1]

 

예시2)

문자열 1: ACP
문자열 2: CAD

DP[N][M]을 구해야 합니다.

 

맨 뒤의 두 문자 비교(P와 D)

두 문자가 동일하지 않다면

그 앞의 문자열을 비교(ACP와 CA 비교, AC와 CAD 비교) -> DP[N-1][M] , DP[N][M-1]

더 큰 것을 고른다 -> MAX()

 

LCS 점화식

문자가 동일할 때: DP[N-1][M-1] + 1
문자가 동일하지 않을 때: MAX(DP[N-1][M], DP[N][M-1])

 

---

문자열 1: ACAK

문자열 2: CKP

로 다시 한 번 해보겠습니다.

 

문자열이 없을 때는 다 0

 

A와 C 비교(다름)

 

A와 문자열X,

C와 문자열X

비교한 것 중 최대값

C와 C 비교(같음)

 

이전 문자열들(A와 문자열X) 확인

 

(A와 문자열X 비교) + (C와 C 동일)

 

 

A와 C 비교(다름)

 

ACA와 문자열X,

AC와 C

비교한 것 중 최대값

 

 

 

...

 

C와 K 비교(다름)

AC와 C 비교(1)

A와 CK 비교(0)

 

K와 K 비교

이전 문자열 비교(ACA와 CK) + 1

 

 

---

코드로 만들어보겠습니다.

 

import sys
iMput = sys.stdin.readline

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

M = len(str1) # 열
N = len(str2) # 행

dp = [[0] * (M+1) for _ in range(N+1)] # 글자 수 + 빈 문자열


for n in range(1, N+1):
    for m in range(1, M+1):
        if str2[n-1] == str1[m-1]: # n과 m 이 1부터 시작해서 -1 해줌
            dp[n][m] = dp[n-1][m-1] + 1
        else:
            dp[n][m] = max(dp[n-1][m], dp[n][m-1])

print(dp[n][m])