[백준 9252] LCS 2 (Python 풀이, Gold IV)

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

9252번: LCS 2

 

 DP 테이블을 만든 뒤, 테이블 역추적으로 LCS 문자열을 복원하는 문제다. 일단 LCS 문제를 푸는 점화식은 잘 알려져 있다.

 

memo[i][j] = memo[i - 1][j - 1] + 1 (if a[i] == b[j])

memo[i][j] = max(memo[i - 1][j], memo[i][j - 1]) (otherwise)

 

 DP 역추적은 이 DP 테이블의 가장 오른쪽 아래에서부터 출발한다. ix = len(a) - 1, jx = len(b) - 1로 놓고, 현재 위치(ix, jx)보다 왼쪽 위에 있으면서 인덱스 차이가 최대 1 나는 칸(ix - 1, jx - 1 // ix - 1, jx // ix, jx - 1)들을 비교하면서 역추적을 해 나간다. 자세한 규칙은 다음과 같다.

 

• 만약 a[ix] == b[jx]라면, memo[ix][jx]는 memo[ix - 1][jx - 1] + 1이라는 공식을 통해 얻어졌을 것이므로, ret에 a[ix] 글자를 추가하고 ix와 jx에 각각 1씩 빼준다.
• 아니면, memo[ix][jx]는 memo[ix - 1][jx], memo[ix][jx - 1] 중 더 큰 쪽에서 왔을 것이므로 더 큰 쪽으로 한 칸 왼쪽 또는 위쪽으로 이동한다.

 이 절차의 시간복잡도는 O(m + n)이다. 이는 dp 전체의 시간복잡도인 O(mn)에 못 미치므로 전체 시간복잡도는 dp의 시간복잡도를 따라간다.

 

a = input()
b = input()

memo = [[-1 for _ in range(len(b))] for _ in range(len(a))]
access = lambda i, j: memo[i][j] if i >= 0 and j >= 0 else 0

for i in range(len(a)):
    for j in range(len(b)):
        if a[i] == b[j]:
            memo[i][j] = access(i - 1, j - 1) + 1
        else:
            memo[i][j] = max(access(i - 1, j), access(i, j - 1))
print(memo[-1][-1])

ret = ''
ix, jx = len(a) - 1, len(b) - 1
while ix >= 0 and jx >= 0:
    if a[ix] == b[jx]:
        ret += a[ix]
        ix -= 1
        jx -= 1
    elif access(ix - 1, jx) > access(ix, jx - 1):
        ix -= 1
    else:
        jx -= 1

print(ret[::-1])