[BOJ 9251] LCS

문제 요약

문제 요약
최장 공통 부분 수열(LCS)를 찾는 문제
두 수열의 부분 수열 중 가장 긴 것을 찾아야 한다.
입력
두 문자열을 2개 줄로 입력받는다 (최대 1000글자)
출력
두 문자열의 LCS의 길이

풀이

첫째 수열<1>의 각 알파벳들을 순서대로 둘째 수열<2>의 모든 알파벳들과 비교한다.
만약 같은 알파벳을 찾으면 바로 <1>의 다음 알파벳으로 넘어간다.
만약 <2>에서 <1>의 현재 알파벳과 같은 알파벳이 없다면 다음으로 넘어간다.
위와 같은 단계를 반복한다.

단 이 단계는 <1>과 <2>의 알파벳 순서를 파라미터로 받은 재귀함수로 실행한다.
각 단계를 실행할 때마다 재귀함수를 call하면 된다.

그럼 어떤 식으로 코드를 짜야할까?

첫째 수열의 index를 depth, 둘째 수열을 recent로 잡는다.
각 자리수에 해당하는 LCS 값을 저장할 배열 M을 선언한다.
DF라는 재귀함수를 선언한다.
depth가 <1>의 끝에 도달하거나 recent가 <2>의 끝에 도달할 시 return한다.
tmp를 선언한 뒤
두 문자가 다르면 현재 tmp값과 M[depth+1][recent]값 중 큰 값을 tmp에 넣는다.
두 문자가 같으면 1 + M[detph+1][i+1]을 넣는다. (이때 i는 같았던 recent 위치)

결과 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def DF(depth, recent):
	# 기저 조건
    if depth == len(A) or recent == len(B):
        return 0
    # M에 LCS 값 기록
    else:
        tmp = 0
        # <2>를 recent부터 끝까지 조사
        for i in range(recent, len(B)):
            if A[depth] == B[i]:
            	# 만약 알파벳이 같을 시
                if M[depth+1][i+1] == -1:
                    M[depth+1][i+1] = DF(depth+1, i+1)
                tmp = 1 + M[depth+1][i+1]
                break
        # 만약 알파벳이 다를 시
        if M[depth+1][recent] == -1:
            M[depth+1][recent] = DF(depth+1, recent)
        tmp = max(tmp, M[depth+1][recent])
        return tmp

A = input().strip()
B = input().strip()
M = [[-1 for i in range(len(B)+1)] for j in range(len(A)+1)]

print(DF(0, 0))

아쉬운 점

다시 LCS를 공부하기 위해 다른 모범 코드들을 찾아봤는데 내 코드가 풀다보니 상당히 번잡하게 짜져 있는 것을 깨달았다...
비슷한 LCS 문제를 좀 더 정돈된 코드로 풀어서 연습해봐야겠다.