백준 9251번: LCS

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

문제 접근

LCS: 최장 공통 부분 수열 을 찾는 문제.

ACAYKP와 CAPCAK의 LCS는 ACAK 이다.
그리고 출력은 이 ACAK의 length 인 4를 출력해주면 된다.

한 문자열을 기준으로 잡고, 한 글자씩 추가하면서 지금까지의 부분 문자열의 'LCS(최장 공통 부분 수열)'이 몇 개인지 기록해나간다.

점화식 :
X[i] == Y[j]일 때
LCS(Xi, Yj) = LCS(Xi - 1, Yj - 1) + 1

X[i] != Y[j]일 때
LCS(Xi, Yj) = LCS(Xi - 1, Yj - 1)
LCS(Xi, Yj) = max(LCS(Xi - 1, Yj), LCS(Xi, Yj - 1))

1. X[i] == Y[j] 인 경우
   먼저 X[i] == Y[j]일 때는 각 문자열에 X[i], Y[j]가 추가되기
   이전의 LCS의 길이(= LCS(Xi - 1, Yj - 1))에 1만큼 더해주면 된다.

2. X[i] != Y[j] 인 경우
   X[i] 와 Y[j]가 같지 않을 때, 각 문자열에 X[i], Y[j]가 추가되기 이전의 LCS의 길이(= LCS(Xi - 1, Yj - 1))를 그대로 가져오면 LCS의 길이를 오차가 있을 수 있다.

문자열 ACB와 ABA를 예로 들어보자. 문자열 ACB와 ABA의 LCS는 AB이다. 하지만 마지막 글자인 'B'와 'A'가 다르다고 LCS(X2, Y2) 일때 LCS를 가져오면 LCS 는 A인 1이 된다.

그래서 우리는 마지막 글자가 다를 때에는 각 문자열의 마지막 글자들이 따로 한 글자씩 추가 되었을 때의
LCS (= LCS(Xi - 1, Yj), LCS(Xi, Yj - 1) ) 중 큰값을 가져와야 한다.

풀이 및 해답

import sys

string_a = ' ' + sys.stdin.readline().rstrip() # 처음을 ' ' 공백으로 받아서 인덱스 1부터 시작하게끔 잡기술
string_b = ' ' + sys.stdin.readline().rstrip() # 처음을 ' ' 공백으로 받아서 인덱스 1부터 시작하게끔 잡기술
# ' 이꼴이됨'

dp = []
for _ in range(len(string_a)):
    row = [0] * len(string_b)
    dp.append(row)
    
for i in range(1, len(string_a)):
    for j in range(1, len(string_b)):
        if string_a[i] == string_b[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]) # 인덱스에서 -1은 마지막 요소를 가르킴