[백준] 9251번 : LCS

문제는 다음과 같습니다.

https://www.acmicpc.net/problem/9251

두 문자열이 주어졌을 때, 두 문자열 모두의 부분 수열이 되는 수열 중 가장 긴 수열인 최장 공통 부분 수열(LCS)을 찾는 문제입니다.

아무리 생각해도 모르겠어서 결국 답을 봤습니다.

풀이의 컨셉은 이렇습니다.

for(int i=1;i<=n;i++){      //두번 째 문자열
	for(int j=1;j<=n;j++){  //첫번 째 문자열
    	LCS 구하기
    }
}

첫번 째 문자열을 T1, 두번 째 문자열을 T2 라고 부르겠습니다.

T1[1~N] 과 T2[1] 의 LCS를 구하고

T1[1~N] 과 T2[1~2] 의 LCS를 구하고 ... T1[1~N] 과 T2[1~N] 의 LCS를 구해나가는 식입니다.

ACAYKP        

CAPCAK 의 LCS

ACAYKP

CAPCAK 의 LCS ...

ACAYKP

CAPCAK 의 LCS

이것을 구할 때 표를 이용하여 구하는데 다음과 같은 규칙을 따릅니다.

T1[j]==T2[i] 일 때, dp[i][j]=dp[i-1][j-1] +1  ->  현재 문자가 LCS에 포함되므로 현재 문자가 나오기 전 LCS에 +1

T1[j]!=T2[i] 일 때, dp[i][j]=max(dp[i-1][j], dp[i][j-1])

-> 현재 문자가 LCS에 포함되지 않으므로 현재 문자가 등장하기 전 LCS 중 큰 값을 대입

이 규칙으로 표를 채우면 다음과 같습니다.

dp[][]		A	C	A	Y	K	P
	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

표를 채운 후 답은 dp[n][n]이 됩니다.