난이도 : 골드 4
유형 : DP, 역추적
https://www.acmicpc.net/problem/9252

문제 접근

두 문자열 A, B가 주어진다.
이때 두 문자열의 최장 공통 부분 수열(LCS) 을 구하고,
그 길이와 LCS 문자열을 출력하는 문제이다.

최장 공통 부분 수열(LCS) 란?

ACAYKP
CAPCAK
의 LCS는 ACAK 이다.

핵심 아이디어

1. dp[i][j] : 문자열 A의 i번째까지와 B의 j번째까지 비교했을 때 LCS의 길이
2. 점화식
   • A[i-1] == B[j-1] → dp[i][j] = dp[i-1][j-1] + 1
     A와 B의 글자가 같다면 이전 dp 테이블에서 + 1
   • 다르면 → dp[i][j] = max(dp[i-1][j], dp[i][j-1])
     다르다면 인접한 두 dp 테이블 중 더 큰 값 가져오기
3. 최종적으로 dp[len(A)][len(B)] 가 LCS 길이.
4. 역추적 : dp 테이블을 뒤에서부터 추적하여 실제 LCS 문자열을 복원.
   A = "ACAYKP"
   B = "CAPCAK"

만약 dp를 다 채우고 복원한다고 해보자.
dp[len_A][len_B] = 4 라고 가정
i = len_A, j = len_B에서 시작:
A[i-1]와 B[j-1] 비교
같으면 LCS에 넣고 대각선으로 이동
다르면 위/왼쪽 중 더 큰 값 쪽으로 이동
이걸 i>0, j>0일 때까지 반복
이렇게 하면 LCS 글자들이 거꾸로 쌓인다.
마지막에 lcs_result.reverse()로 뒤집으면 정답!

해답 및 풀이

import sys
input = sys.stdin.readline

A = input().strip() # len(A), len(B) 구할 때 줄바꿈 개행 \n 까지 세서 +1 될 수 있기 .strip() 을 붙여줘야 한다.
B = input().strip()  
 
len_A, len_B = len(A), len(B)

# 0 인덱스를 포함해서 (len_A+1) x (len_B+1) 크기의 테이블이 필요
# dp[i][j] 는 A의 i글자, B의 j글자까지 고려했을 때, LCS 길이
dp = []

for i in range(len_A + 1):
    row = []
    for j in range(len_B + 1):
        row.append(0) # 초기값 0 
    dp.append(row) 

# dp = [[0] * (len_B + 1) for _ in range(len_A + 1)] 이렇게 한줄로도 쓸 수 있다.

# DP 테이블 채우기
for i in range(1, len_A + 1):
    for j in range(1, len_B + 1):
        if A[i-1] == B[j-1]: # 인덱스 0 부터 시작하니까 i번째는 i-1 로 처리해준 것
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # 위쪽, 왼쪽 중 큰 값 선택

# LCS 길이 출력
print(dp[len_A][len_B])

# LCS 문자열 복원
lcs_result = []

while len_A > 0 and len_B > 0:
    if A[len_A - 1] == B[len_B-1]: # 문자가 같다면
        lcs_result.append(A[len_A-1])
        len_A -= 1
        len_B -= 1

    else:
        if dp[len_A-1][len_B] >= dp[len_A][len_B-1]:
            len_A -= 1
        else:
            len_B -= 1


lcs_result.reverse()
if lcs_result:
    print(''.join(lcs_result))

https://think-tech.tistory.com/55
위 블로그에 이해하기 쉽게 잘 설명되어있어 참고하였다.