백준 - LCS [9251]

예를들어, $X_n$ = { $X_1$ , $X_2$ , ... $X_n$ } , $Y_n$ = { $Y_1$ , $Y_2$ , ... $Y_n$ } 가 있다고 치자. 그때 LCS( $X_n$ , $Y_n$ ) = $X_n$ , $Y_n$ 의 최장 길이 공통 부분 수열의 길이이다.

이제 LCS(i, j)일 때를 보면 $X_i$ = $X_1$ , $X_2$ , ... , $X_i$ 와 $Y_j$ = $Y_1$ , $Y_2$ , ... , $Y_j$ 가 나온다. 여기서 $X_i$ 와 $Y_j$ 가 같을 때와 다를 때를 확인하면 된다.

$X_i = Y_j$ 일 때 즉, 마지막 문자가 같은 경우 그 이전까지 구한 LCS(i-1, j-1) 에 +1 를 해주면 된다.

하지만 $X_i$ != $Y_j$ 일 때 (다른 경우) X의 마지막 문자 혹은 Y의 마지막 문자 중 하나가 뽑힐 때를 생각해볼 수 있다. (둘 다 동시에 뽑는 경우는 없다.) 즉, X의 마지막 문자가 뽑힌 경우에는 Y의 마지막 문자가 전까지의 LCS 와 Y의 마지막 문자가 뽑힌 경우 X의 마지막 문자 전까지의 LCS 2가지가 나올 수 있다.

다시 정리하면 LCS(i, j-1) 과 LCS(i-1, j) 이 2가지에서 제일 긴 것을 찾으면 된다.

점화식을 세우면, 아래와 같다.

LCS(i, j) =

LCS(i-1, j-1) + 1 if $X_i = Y_i$

max(LCS(i, j-1) , LCS(i-1, j)) if $X_i$ != $Y_j$

이제 주어진 예제를 가지고 표를 그려 확인해보자. 최종적으로는 제일 오른쪽 밑에 있는 값이 답이다.

str1 / str2	0	C	A	P	C	A	K
0	0	0	0	0	0	0	0
A
C
A
Y
K
P

여기서 0은 빈 문자열을 의미한다. 이제 행단위로 하나씩 채워나가게 되면 아래와 같이 채워질 수 있다.

str1 / str2	C	A	P	C	A	K
0	0	0	0	0	0	0
A	0	1	1	1	1	1
C	1	1	1	2	2	2
A	1	2	2	2	3	3
Y	1	2	2	2	3	3
K	1	2	2	2	3	4
P	1	2	3	3	3	4

왼쪽위를 (1,1)로 보고 (4,3) 위치를 설명하겠다.
(4,3) 은 str1 의 A와 str2 의 A 를 비교하는 것인데, A == A 이기 때문에 (4-1, 3-1) + 1를 해주어 2가 채워짐을 알 수 있다.

추가적으로 (4,2)위치를 보면 str1의 A와 str2의 C와 비교하니 다르다는 것을 알았고 이때, (4,2-1) = 0 과 (4-3, 2) = 1 중에 최대가 1이기 때문에 1로 채워짐을 알 수 있다.

따라서 LCS = 4 가 나옴을 알 수 있다.

해당 점화식을 코드로 옮겼으니 확인하면 되겠다.

소스

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		char[] str1 = sc.nextLine().toCharArray();
		char[] str2 = sc.nextLine().toCharArray();

		int[][] dp = new int[str1.length + 1][str2.length + 1];

		for (int i = 1; i <= str1.length; i++) {
			for (int j = 1; j <= str2.length; j++) {

				// 같을 경우
				if (str1[i - 1] == str2[j - 1]) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}
				// 같지 않을 경우
				else {
					dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
				}
			}
		}

		System.out.println(dp[str1.length][str2.length]);

	}

}