백준 9251 LCS

1. 해를 분석해서 부문제로 분할하기
2. 부문제의 해로 큰 문제의 해를 표현(점화식)
3. 부문제들의 해를 가지고 있는 dp table을 채우기
4. table에서 해를 계산하여 알고리즘의 correctness 검증

stringA : ACAYKP stringB: CAPCAK

An과 Bm의 최장길이 공통 부문자열의 길이를 구해야 함 이를 어떻게 작은 문제들로 쪼갤 수 있을까? LCS(i,j) ⇒ Ai과 Bj의 LCS 길이 Ai와 Bj가 서로 같다면 최장길이 공통 문자열에 추가된다. 이는 곧 이 두 문자열을 비교했을 때, 두 문자열이 서로 같다면 길이가 1 증가한다는 뜻이다. 나머지는

• A1,A2,…Ai-1
• B1,B2,…Bj-1 로 나뉘어 질 수 있다. 그렇다면 이 문자열들에 대해서도 계속 공통 문자열을 비교하면서 나아가면 되지 않을까?
• 마지막 두 문자열이 같을 때 : LCS(i,j) = LCS(i-1,j-1) + 1 라고 볼 수 있다. 하지만 마지막 두 문자열이 다를 때는 간단하게 LCS(i,j) = LCS(i-1,j-1)라고만 생각하면 안된다. 왜냐면 나중에 A의 마지막 문자열이 포함되어 있지만 B의 마지막 문자열은 포함되어 있지 않을 수 있고, B의 마지막 문자열이 포함되어 있지만 A의 마지막 문자열을 포함되어 있지 않을 수 있기 때문이다. (여기서 A,B문자열이 모두 같은 경우는 이미 아니기 때문에 제외한다) 그렇기 때문에 우리가 원하는 LCS는 LCS(i,j-1) 과 LCS(i-1,j) 중 더 길이가 긴 것으로 선택해야 한다.

그렇다면 이 LCS(i,j-1)과 LCS(i-1,j)를 미리 구해놔야 한단 소리기 때문에 dp 테이블을 만들어서 이에 대한 값을 메모이제이션 해놓으면 된다.

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4