[백준]동적 계획법1/LCS/9251 풀이 JAVA

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다.

문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

풀이(JAVA)

예제인 ACAYKP와 CAPCAK의 LCS 길이를 찾아보자.

 

아래 표는 이차 배열인 dp를 나타낸 것이다.

str1은 ACAYKP, str2는 CAPCAK이다.

str1의 A는 0번째 문자, C는 2번째 문자란 것을 0-A, 1-C << 이렇게 표현했다.

 

dp[3][2]는

str1의 3번째 글자까지인 ACAY와

str2의 2번째 글자까지인 CAP의

LCS길이인 2를 담고있다. ({C, A}로 길이는 2다)

 

dp[1][1]은 AC와 CA의 LCS는 {C}또는 {A}인데 이때는 str1에 먼저 나온 글자로 표를 채웠다.

 

(이때 LCS 길이가 {A, C}로 2라고 생각할 수도 있지만...

str1의 AC의 순서대로 str2의 LCS를 찾기 때문에 하나가 맞다.

예를 들면

예제인 ACAYKP와 CAPCAK도 LCS가 ACAK인데, ACAYKP, CAPCAK 이렇게 str1의 순서대로 찾기 때문에

str1과 str2 모두 P가 들어가지만 순서가 다르기 때문에 잘리는 것이다.)

 

dp[str1][str2]	0-A	1-C	2-A	3-Y	4-K	5P
0-C	0 {}	1 {C}	1 {C}	1 {C}	1 {C}	1 {C}
1-A	1 {A}	1 {C}	2 {C, A}	2 {C, A}	2 {C, A}	2 {C, A}
2-P	1 {A}	1 {C}	2 {C, A}	2 {C, A}	2 {C, A}	3 {C, A, P}
3-C	1 {A}	2 {A, C}	2 {A, C}	2 {A, C}	2 {A, C}	3 {C, A, P}
4-A	1 {A}	2 {A, C}	3 {A, C, A}	3 {A, C, A}	3 {A, C, A}	3 {C, A, P}
5-K	1 {A}	2 {A, C}	3 {A, C, A}	3 {A, C, A}	4 {A, C, A}	4 {A, C, A, K}

 

우리가 구하고자 하는 것은 dp[5][5]이다.

이를 재귀로 표현하는 방법은 아래 코드와 같다.