5.6 최장 공통 부분 수열 출력하기

이번 절은 지난 절에서 구한 최장 공통부분 수열 개수 구하기의 확장판이다.
(https://www.acmicpc.net/problem/9252)

지난 절에서는 개수만 구했지만, 이번에는 어떤 문자인지도 출력하는 문제다.
캐시를 만들어 나가면서 최장 공통부분 수열을 구하면 되는 걸로 생각했는데,
그게 아니라 일단 캐시를 다 만들고 끝에서부터 다시 역으로 찾아 들어가는(백 트레킹) 방식을 사용한다.

결국은 DP로 캐시를 못 만들면 아무것도 못함.. ㅠㅠ

로직은 다음과 같다.
1. (m, n)에서 시작하되, i와 j가 동일하면 LCS에 포함 후 i-1, j-1로 이동.
2. i와 j가 다르면 ar[i]와 ar[j] 중 큰 값으로 이동.
3. 0, 0까지 도달할 때까지 반복
위의 로직을 코드로 옮기면 다음과 같다.

def solve(a, b):
    m, n = len(a), len(b)

    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 a[j - 1] == b[i - 1]:
                cache[i][j] = cache[i - 1][j - 1] + 1
            else:
                cache[i][j] = max(cache[i - 1][j], cache[i][j - 1])

    res = ''

    j, i = m, n
    while i > 0 and j > 0:
        if a[j - 1] == b[i - 1]:
            res += a[j - 1]
            i -= 1
            j -= 1
        elif cache[i - 1][j] > cache[i][j - 1]:
            i -= 1
        else:
            j -= 1

    print(cache[n][m])
    print(res[::-1])

    return True


if __name__ == '__main__':
    a = input()
    b = input()
    solve(a, b)

BOJ에 제출해서 PASS 됨.
백트래킹이라고 하면 되게 막연했었는데
이번 기회를 통해서 좀 익숙해진 듯하다.

일단 DP로 캐시 배 열등을 구한 다음에
끝에서부터 다시 더듬어가면서 찾는 형식으로 가면 될 듯.
그리고 딱 캐시만 쓰는 건 아니고 처음에 받았던 데이터(문자열)도 사용하는 걸 알게 됨.