[백준][DP][LCS] 9251. LCS(최장공통부분수열)

9251. LCS

9251번: LCS

 

• 풀이
  • 아래 설명 보고 원리 이해
  • LCS(Xi, Yj)를 문자열 X, Y 각각의 i, j번째 글자까지의 최장 공통 부분 문자열의 길이라고 했을 때

X[i] == Y[j]일 때 : LCS(Xi, Yj) = LCS(Xi - 1, Yj - 1) + 1
X[i] != Y[j]일 때 : LCS(Xi, Yj) = max(LCS(Xi - 1, Yj), LCS(Xi, Yj - 1))

https://velog.io/@piopiop/%EB%B0%B1%EC%A4%80-9251-LCS-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준 9251] LCS (파이썬)

 

a = list(input().rstrip())
b = list(input().rstrip())
n = len(a)
m = len(b)
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        if a[i-1] == b[j-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[n][m])