문제출처 : https://www.acmicpc.net/problem/9251

---

문제 파악

최장 공통 부분 수열, LCS의 길이를 출력해야 한다.

LCS란, 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것

ACAYKP
CAPCAK
의 LCS는 ACAK이다.

어떻게 풀 수 있을까

---

첫 문자열을 A, 두번째 문자열을 B, 그리고 각각의 길이를 n,m 이라고 했을때
dp[i][j] 를 이렇게 정의할 수 있다.

"A의 앞에서부터 i글자, B의 앞에서부터 j글자까지 고려했을 때 LCS의 길이"

점화식은 두 경우로 나뉜다.
1) 마지막 문자가 같을 때
A[i-1] == B[j-1] 라면,
이 문자를 공통 수열에 포함시킬 수 있으므로
dp[i][j] = dp[i-1][j-1] + 1

예시로 알아보자
A = "ABC"
B = "AHC"

i = 3 → A[i-1] = 'C'
j = 3 → B[j-1] = 'C'

둘 다 마지막 글자가 'C'.

그러면:
A[0..1] = "AB"
B[0..1] = "AH"

이 둘의 LCS = "A" → 길이 1 → dp[2][2] = 1
이제 마지막 글자가 'C'로 같으니까
LCS = "A" + "C" = "AC"
길이 = 2 → dp[3][3] = dp[2][2] + 1 = 2

---

2) 마지막 문자가 다를 때
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
이는 A쪽에서 한글자 버리거나, B쪽에서 한글자 버린것 중 더 큰 dp값을 dp[i][j]에 대입하는 의미이다.

예시를 본다면

A = "ABC"
B = "ACD"

우리가 계산하고 싶은 위치는:

i = 3 (A[2] = 'C')
j = 3 (B[2] = 'D')

'C' != 'D' → 마지막 문자가 다르는 케이스, dp[3][3] 계산.

케이스 1 : A의 마지막 문자 'C'를 버리고 비교:

A: "AB"
B: "ACD"

이 둘의 LCS는 "A"
→ 길이 1

케이스 2 : B의 마지막 문자 'D'를 버리고 비교:

A: "ABC"
B: "AC"

LCS는 "AC"
→ 길이 2

이렇듯 마지막 문자가 다르다면, 하나씩 떼서 더 큰것을 dp로 가진다.

해답 코드

import sys
input = sys.stdin.readline

A = input().strip()
B = input().strip()

N = len(A)
M = len(B)

# dp[i][j] = "A의 앞에서부터 i글자, B의 앞에서부터 j글자까지 고려했을 때 LCS의 길이"
dp = []
for _ in range(N+1):
    row = [0] * (M+1)
    dp.append(row)

# 마지막 문자가 같을 때, dp[i][j] = dp[i-1][j-1] +1
# 다를 때, 
for i in range(1,N+1):
    for j in range(1,M+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[N][M])

• sys.stdin.readline 으로 문자열을 입력받았을 때는 strip() 붙여주기 , 공백이 뒤에 붙는다.
• 이중 반복문에서 초기값을 dp식에 넣어보기 -> i, j 를 0부터 시작할 경우 dp[-1][-1] 이 나와 인덱스 에러가 나오니 1부터 N+1 로 범위 잡아주기