9251. LCS (Python)

9251번: LCS

 

풀이

 LCS 알고리즘의 대표적인 문제다. LCS 알고리즘에 대해서는 여기를 참고하자.

 

 

코드

if __name__ == '__main__':
    str1 = input()
    str2 = input()

    dp = [[0 for _ in range(len(str1) + 1)] for _ in range(len(str2) + 1)]

    for i in range(1, len(str2) + 1):
        for j in range(1, len(str1) + 1):
            if str1[j-1] == str2[i-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[len(str2)][len(str1)])