[백준 9251] LCS

0. 제목

• 백준 9251 LCS
• BOJ 9251 LCS
• 파이썬 9251 LCS
• Python 9251 LCS

---

1. 문제

www.acmicpc.net/problem/9251

9251번: LCS

---

2. 풀이

• 두 문자열의 길이를 조금씩 늘려 가며 확인하여 공통 부분 수열의 최대 길이를 계산한다.
• 두 문자열을 X, Y라고 할 때 X[i-1] = Y[i-1] 이면 dp[i] = dp[i-1][j-1] + 1, X[i-1] != Y[i-1] 이면 dp[i] = max(dp[i-1][j], dp[i][j-1]) 이다.

---

3. 코드

x = input()
y = input()
 
dp = [[0] * (len(y) + 1) for _ in range(len(x) + 1)]
 
for i in range(1, len(x) + 1):
    for j in range(1, len(y) + 1):
        if x[i - 1] == y[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
            
print(dp[len(x)][len(y)])