[백준] 9251 : LCS

문제

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

참고 자료

https://www.youtube.com/watch?v=EAXDUxVYquY&ab_channel=Chan-SuShin

DP 문제 푸는 법

1. 해 분석. 부분제로 분할
2. 부분제의 해 -> 큰 문제의 해로 표현 (점화식)
3. 적당한 순서로 table 채우기
4. table에서 해를 계산하여 알고리즘의 correctness 증명

다음 내용 중, 마지막 문자가 같은 경우 LCS(i-1, j-1) + 1로 점화식 수정
마지막 문자가 다른 경우 LCS[i][j-1]은 A는 다 들어가고 B의 마지막 원소를 부분 수열에 안 넣을 때
LCS[i-1][j]는 A의 마지막 원소를 부분 수열에 안 넣고 B를 다 넣을 때 중 max로 더 큰 경우를 고르는 것이다.

직접 그려본 dp 테이블

dp[i][j]는 문자열 x, y 각각의 i, j번째 글자까지 최장 공통 부분 문자열의 길이

풀이

dp 테이블인 lcs[i][j]는 각각 x가 i개이고 y가 j개일 때 최장 부분 수열의 길이를 값으로 가진다.

import sys
input = sys.stdin.readline

x = [0] + list(input().rstrip()) # strip()은 양쪽 공백 삭제, rstrip()은 오른쪽 공백 삭제
y = [0] + list(input().rstrip())

# 2차원 배열 선언
lcs = [[0 for col in range(len(y))] for row in range(len(x))] 

# 구해야 하는 것
# lcs[len(x)-1][len(y)-1]

# 점화식
# 두 값이 같으면 lcs[i-1][j-1] + 1
# 두 값이 다르면 max(lcs[i-1][j], lcs[i][j-1])

for i in range(1, len(x)):
    for j in range(1, len(y)):
        if x[i] == y[j]:
            lcs[i][j] = lcs[i-1][j-1] + 1
        else:
            lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1])
       
print(lcs[len(x)-1][len(y)-1])