[알고리즘 문제풀이] LCS

문제 제목 : LCS

문제 난이도 : 하

문제 유형 : 동적 프로그래밍, 문자열, LCS

https://www.acmicpc.net/problem/9251
시간 제한 : 0.1초
메모리 제한 : 256MB

문제풀이 아이디어

< 소스 코드 >

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)])