5.5 최장 공통 부분 수열 길이 구하기 - 재귀

최장 공통부분 수열에 대한 내용은 아래를 참조.
(https://ko.wikipedia.org/wiki/최장_공통_부분_수열)

길이가 n인 문자열의 부분 수열의 개수는 2^n.
최적의 하위 구조를 가지고 있는 문제로 재귀로 풀어볼 수 있음.
가장 마지막 문자열을 비교하되,

1. 두 글자가 같은 경우 : 선택된 글자가 LCS의 마지막 글자가 됨. 매우 자명함. 결과에 1을 더하고 양쪽 문자열에서 선택된 글자를 삭제한 문자열로 함수를 재귀 호출
2. 두 글자가 다른 경우 : 다음 두 LCS의 길이를 구해서 이 중 큰 값을 반환.
2-1. 첫 번째 문자열에서 마지막 글자를 제외한 문자열과 두 번째 문자열의 LCS.
2-2. 첫 번째 문자열과 마지막 글자를 제외한 두 번째 문자열의 LCS.
위의 내용을 코드로 옮기면 다음과 같다.

import sys
sys.setrecurtionlimit(10**6)

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

	if m == 0 or n == 0:
		return 0

	if a[-1] == b[-1]:
		return 1 + solve(a[:-1], b[:-1])
	else:
		return max(solve(a, b[:-1]), solve(a[:-1], b))


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

	print(solve(a, b))

파이썬의 경우는 리스트의 마지막 인덱스에 접근하는 방법이 매우 간단해서(-1로 접근하면 됨)

생각보다 코드가 엄청 간단하다. 정말 로직 그대로를 구현한 듯한 느낌.