Baekjoon 9251.py [LCS]

문제가 궁금하다면?

내 풀이

import sys
input = sys.stdin.readline

w1 = input().rstrip()
w2 = input().rstrip()
lenOfw1 = len(w1)
lenOfw2 = len(w2)
dp = [[0]*(lenOfw2+2) for _ in range(lenOfw1+2)]
result = 0

for i in range(2, lenOfw1+2):
    for j in range(2, lenOfw2+2):
        dp[i-1][j-1] = max(dp[i-2][j-2], dp[i-1][j-2], dp[i-2][j-1], dp[i-1][j-1])
        if w1[i-2] == w2[j-2]:
            dp[i][j] = dp[i-1][j-1] + 1
            result = max(dp[i][j], result)
print(result)

풀이 복기

현재 문자가 같다면 이전 dp + 1을 해주는 로직은 바로 생각났다. 하지만 바로전이 아닌 예전 문자에 같은문자가 있었다면 그때의 dp + 1을 해서 현재dp에 저장해야 하기때문에 이 방법을 구현하는데 오래걸렸다.

물음표 자리에는 빨간색 네모칸의 최댓값+1 을 저장하기위해
dp[i-1][j-1] = max(dp[i-2][j-2], dp[i-1][j-2], dp[i-2][j-1], dp[i-1][j-1])로 저장했다.

이를 사용해서 index가 0,0부터 계속 최댓값이 dp[i-1][j-1]에 저장되므로 현재 dp[i][j] = dp[i-1][j-1]+1에는 최댓값만 저장된다.