티스토리 뷰

Algorithm/Baekjoon

[백준] 9251 : LCS - Python

Dev.sohee 2020. 6. 27. 23:55

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

 

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

s1 = list(input())
s2 = list(input())

s1_len = len(s1)
s2_len = len(s2)

dp = [[0] * (s2_len+1) for _ in range(s1_len + 1)]

for i in range(s1_len):
    for j in range(s2_len):
        if s1[i] == s2[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
        
print(dp[s1_len][s2_len])
공지사항
최근에 올라온 글
«   2025/02   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
글 보관함