[백준 BOJ_9251] LCS Python 풀이

출처: 백준 온라인 저지

문제

풀이

예시로 주어진 문자열을 비교하는 표를 만들어보았습니다.

이 표가 그대로 memoization을 위 한 cache가 됩니다.

비교하는 문자가 같을 경우 이전의 공통부분(cache[i-1][j-1])에 문자를 추가해주어야 합니다. 문자가 같지 않을 경우에는 두 이전 문자열의 공통부분(cache[i][j-1], cache[i-1][j]) 중 큰 값으로 저장해줍니다.

코드

S1 = input()
S2 = input()
N = len(S1)
M = len(S2)
cache = [[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 S1[i-1] == S2[j-1]:
            cache[i][j] = cache[i-1][j-1] + 1
        else:
            cache[i][j] = max(cache[i-1][j], cache[i][j-1])
print(cache[N][M])