백준 9251: LCS

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

입출력 분석

• 시간 제한이 0.1초이지만, 입력이 1000이므로 O(N^2)를 적용해도 10^6 < 10^7(0.1초) 가능
• 따라서 어떻게 LCS를 구현할 것인지 아이디어를 떠올리는 것이 중요

알고리즘 분석

• 두 문자열을 바탕으로 2차원 배열을 만들어서 DP로 해결

---

핵심 아이디어

두 알파벳이 동일한 경우

• 왼쪽 대각선의 값 + 1
• 둘 다 뺀 왼쪽 대각선의 값에 +1을 한다
• ex) CAPCA와 ACA에서 마지막 A가 일치 -> CAPC와 AC의 값인 2에 +1

두 알파벳이 다른 경우

• max(왼쪽 값, 위쪽 값)
• 둘 중 하나를 빼고 계산한 값을 가져와서 최대값을 유지한다
• ex) CAPCA와 ACAY에서 일치하지 않음 -> CAPCA와 ACA / CAPC와 ACAY 값 중 최대값 선택

해당 점화식을 바탕으로 마지막까지 계산을 진행했을 때 나오는 값이 정답이 된다.

---

풀이

import sys

input = sys.stdin.readline

A = input().strip()
B = input().strip()

LCS = [[0] * (len(B) + 1) for _ in range(len(A) + 1)]

for i in range(1, len(A) + 1):
    for j in range(1, len(B) + 1):
        if A[i - 1] == B[j - 1]:
            LCS[i][j] = LCS[i - 1][j - 1] + 1
        else:
            LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

print(LCS[-1][-1])

---

결과

점화식을 구하는 아이디어가 생소한 유형이라 까다롭게 느껴졌다.

---

역추적 코드

LCS가 어떤 문자열인지 궁금하다면, 끝에서부터 역추적을 통해 아래와 같이 구할 수 있다.

# 이전 코드는 동일

i, j = len(A), len(B)
result = []

while i > 0 and j > 0:
    if A[i - 1] == B[j - 1]:
        result.append(A[i - 1])
        i -= 1
        j -= 1
    else:
        if LCS[i - 1][j] > LCS[i][j - 1]:
            i -= 1
        else:
            j -= 1

print("".join(result[::-1]))

결과

LCS의 길이와 문자까지 확인할 수 있다.