[알고리즘][Python] 백준 9251 LCS 문제 풀이

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

9251번: LCS

---

문제 해석 : LCS는 공통된 가장 긴 공통 문자열을 찾는 알고리즘이다. 이 문제에서는 실제 LCS 문자열을 출력하는 대신 길이를 구하면 된다.

 

문제 풀이 : DP를 활용해서 가능한 경우를 모두 메모하면서 계산한다.

---

풀이 코드

S1 = list(input())
S2 = list(input())

S1_length = len(S1)
S2_length = len(S2)

dp = [[0] * (S2_length + 1) for _ in range(S1_length +1)]

for i in range(S1_length):
    for j in range(S2_length):
        if S1[i] == S2[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

print(dp[S1_length][S2_length])

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.