[BaekJoon] 백준 9251번 : LCS

9251번 : LCS

정말 어려웠던 문제여서 한참을 고민하다 다른 사람 풀이를 참조하여 풀었다..

[백준] 9251번 C/C++ 풀이 _ LCS

우선 이 표를 이해하는게 가장 중요하다.

ACAYKP CAPCAK 의 LCS 를 구하는 과정인데 DP 를 사용한다.

표의 원소는 각 문자열로 만들수 있는 LCS 의 길이를 의미한다.

예를 들어 4행 4열을 보게 되면 CAP ACA 의 LCS 길이를 갖고있다.

이렇게 주어진 문자열을 쪼개서 C A 의 LCS 부터 CAPCAK ACAYKP 의 LCS 를 구해가면 된다.

표를 채우는 규칙은 두 개의 문자열 끝 값이 같을 땐 표의 좌상단 값에 1을 더하고

문자열 끝 값이 다를 땐 상단과 왼쪽 값 중 큰 값을 넣으면 된다.

빨간색 형광펜이 칠해져 있는 것이 두 개의 문자열 끝 값이 다른 경우이고

초록색 형광펜이 칠해져 있는 것이 두 개의 문자열 끝 값이 값은 경우이다.

이런 풀이를 생각하는 사람은 문제를 많이 풀어서 보이는 걸까.. 태어날 때 부터 머리가 좋아서 풀이법이 바로 보이는 걸까..

---

arr1 = input()
arr2 = input()
dp = [[0 for _ in range(len(arr1) + 1)] for _ in range(len(arr2) + 1)]

for i in range(1, len(arr2) + 1):
	for j in range(1, len(arr1) + 1):
		if arr1[j - 1] == arr2[i - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

print(dp[len(arr2)][len(arr1)])