[BaekJoon] 9252번 : LCS 2

9252번 : LCS 2

[BaekJoon] 백준 9251번 : LCS 의 두 번째 문제이다.

9251번은 LCS 의 길이만 구하면 됐지만 이 문제는 길이와 함께 LCS 를 반환해야 한다.

길이만 구할때는 문자열 길이만 가지고 dp 를 했다면 이번에는 길이 대신 문자열 자체를 가지고 dp 를 수행하면 된다.

알고리즘은 비교하는 문자가 다르면 현재 위치에서 왼쪽, 위쪽 중 긴 문자열을 그대로 가져오고

문자가 같다면 왼쪽 위 대각선 위치의 문자열과 현재 문자열을 더한다.

행렬로 그려서 표현하면 다음과 같다.

---

def solution():
	len_fisrt = len(first)
	len_second = len(second)
	dp = [[''] * (len_fisrt + 1) for _ in range(len_second + 1)]

	for i in range(1, len_second + 1):
		for j in range(1, len_fisrt + 1):
			if second[i - 1] == first[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + second[i - 1]
			else:
				if len(dp[i - 1][j]) < len(dp[i][j - 1]):
					dp[i][j] = dp[i][j - 1]
				else:
					dp[i][j] = dp[i - 1][j]

	print(len(dp[len_second][len_fisrt]))
	print(dp[len_second][len_fisrt])
	return


if __name__ == '__main__':
	first = input()
	second = input()

	solution()