백준 알고리즘 9251. LCS

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

9251번: LCS

 

전체 코드

s_w = input()
s_h = input()

w = len(s_w)
h = len(s_h)

# (w+1) x (h+1) dp 테이블을 생성한다.
dp = [[0] * (w + 1) for _ in range(h + 1)]

for i in range(1, h + 1):
    for j in range(1, w + 1):
        # 문자열이 동일하면 좌, 상단 개수 + 1로 갱신한다.
        if s_h[i - 1] == s_w[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[-1][-1])